Problem

4 /8


chặt cây

Problem

Chubaty dạy Grigory Melekhov cách thực hiện đòn Baklan bằng kiếm. Là mục tiêu, chúng sử dụng n cây liên tiếp, được đánh số từ 1 đến n. Chubaty, ước tính sức mạnh của tất cả các cây bằng số tự nhiên và viết chúng ra. Đối với mỗi cây mà Melekhov chặt được, anh ta nhận được một số điểm bằng với số ghi trên cây, và nếu không chặt được, anh ta sẽ mất số điểm tương ứng.

Chubaty yêu cầu Grigory đánh các cây từ l đến r, theo thứ tự số lượng tăng dần. Melekhov gần đây bị đau vai, vì vậy anh ấy có thể chặt cây thành công mọi lúc, tức là nếu anh ấy chặt được cây có số i, thì anh ấy sẽ không thể chặt được cây có số < mã>i + 1, nhưng sẽ có thể chặt cây bằng số i + 2, v.v.

Chubat m từng yêu cầu Grigory thực hiện các cú đánh, nhưng anh ta quên mất Melekhov có thể chặt những cây gì. Giúp anh ấy xác định số điểm Gregory ghi được cho mỗi lần thử.
 
Đầu vào
Dòng đầu tiên chứa 2 số n và m (\(1 <= n, m <= 100000 \))
Dòng thứ hai chứa số n - sức mạnh của tất cả các cây, trong đó sức mạnh của cây i được viết tại vị trí i.
Các dòng m sau chứa các cặp số l và r (\(1 < ;= l <= r <= n\)), nghĩa là đoạn cây mà Chubaty yêu cầu chặt hạ.
 
Đầu ra
Đối với mỗi truy vấn, hãy in số điểm mà Grigory kiếm được trong lần thử này.
 

 

Ví dụ
<đầu>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Đầu vào Đầu ra
1
6 6
1 2 3 4 5 6
16
1 5
2 6
2 5
2 4
2 2
-3
3
4
-2
3
2