Bedan Contest #01 - B - Trò chơi với bi

Điểm: 1700 (thành phần)

Thời gian: 0.5s

Bộ nhớ: 16M

Input: marble.inp

Output: marble.out

Tác giả:

flo

Dạng bài

Ngôn ngữ cho phép

C++, ~~NASM~~, Pascal, pypy3, Python

Quá rảnh rỗi, flo nhớ lại hồi cậu đi chơi ở công viên Châu Phi. Hồi đó, cậu và cô người yêu của cậu vẫn còn yêu nhau say đắm. Một ký ức đẹp như vậy làm flo chìm đắm vào nó. Bỗng cậu nhớ có một trò chơi đã hại não của cậu và cả cô người yêu của cậu khiến cho cậu vẫn còn ám ảnh đến bây giờ. Trò chơi ấy có nội dung như sau.

Nội dung trò chơi

Cho $1$ dãy bi gồm $n$ viên bi, viên thứ $i$ có số điểm là $a_i$ . Bạn sẽ có $m$ lượt chơi và tại mỗi lượt, bạn phải loại bỏ một số viên bi trong đoạn $[l, r]$ sao cho độ đẹp của các viên bi còn lại của đoạn $[l, r]$ là lớn nhất.

Độ đẹp của một dãy $a$ gồm $n$ viên bi được định nghĩa là $a_1 - a_2 + a_3 - ... + (-1)^{n-1} \times a_n$ .

flo bỗng nhớ lại sự đau đơn khi trò chơi ấy. Bạn có vẻ rảnh rỗi như flo nên cậu ấy muốn bạn thử sức với trò chơi này. Bạn hãy đồng ý và thử sức nhé.

Input, Output and Scoring

Input

Hai nguyên dương $n, m$ $(1 \le n, m \le 10^5)$ .
Dãy $a$ gồm $n$ viên bi với các số điểm $a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^9)$ .
$m$ dòng tiếp theo, mỗi dòng gồm $2$ số nguyên dương $l, r$ $(1 \le l \le r \le n)$ .

Output

Với mỗi lần chơi, hãy in ra độ đẹp của các viên bi lớn nhất có thể của đoạn $[l, r]$ .

Scoring

Subtask $1$ $(10\%)$ : $1 \le n, m \le 20$ .
Subtask $2$ $(30\%)$ : $1 \le n, m \le 10^3$ .
Subtask $3$ $(60\%)$ : Không giới hạn gì thêm.

Example

Input

Output

5
11

Note

Ở lượt chơi $1$ , ta có thể loại bỏ viên bi thứ $1$ của đoạn $[1, 4]$ . Độ đẹp của các viên bi là $4-2+3 = 5$ .
Ở lượt chơi $2$ , ta có thể loại bỏ viên bi thứ $3$ của đoạn $[2, 5]$ . Độ đẹp của các viên bi là $4-2+9 = 11$ .

Bình luận

Không có bình luận nào.