Module: Jumlah awalan


Problem

4 /8


penebangan pokok

Problem

Chubaty mengajar Grigory Melekhov cara melakukan serangan Baklan dengan pedang. Sebagai sasaran, mereka menggunakan pepohon n berturut-turut, bernombor daripada 1 hingga n. Chubaty, menganggarkan kekuatan semua pokok dengan nombor semula jadi, dan menulisnya. Bagi setiap pokok yang Melekhov dapat potong, dia menerima sejumlah mata yang sama dengan nombor yang tertulis pada pokok itu, dan jika tidak dapat, dia kehilangan jumlah yang sama.

Chubaty meminta Grigory untuk memukul pokok dari l hingga r, dalam tertib menaik bagi nombor mereka. Melekhov baru-baru ini mencederakan bahunya, jadi dia boleh berjaya menebang pokok setiap kali, iaitu jika dia menebang pokok dengan nombor i, maka dia tidak akan dapat menebang pokok dengan nombor < kod>i + 1, tetapi akan dapat menebang pokok dengan nombor i + 2 dsb.

Chubat m pernah meminta Grigory untuk melakukan pukulan, tetapi dia terlupa pokok apa yang boleh ditebang oleh Melekhov. Bantu dia menentukan jumlah mata yang dijaringkan Gregory untuk setiap percubaan.
 
Input
Baris pertama mengandungi 2 nombor n dan m (\(1 <= n, m <= 100000 \))
Baris kedua mengandungi nombor n - kekuatan semua pokok, dengan kekuatan i pokok ditulis pada kedudukan i.
Barisan m berikut mengandungi pasangan nombor l dan r (\(1 < ; = l <= r <= n\)), maksudnya sekeping pokok yang Chubaty minta ditebang.
 
Output
Untuk setiap pertanyaan cetak berapa banyak mata yang diperoleh Grigory dalam percubaan ini.
 

 

Contoh

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!

# Input Output
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