Cho dãy số nguyên dương ~a~. Với mỗi truy vấn ~(u, v)~, hãy chia đoạn ~a_u, \ldots, a_v~ thành hai phần liên tiếp, phần bên phải có thể rỗng, sao cho độ chênh lệch tổng hai phần là nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa ~n~ và ~q~.

Dòng thứ hai chứa ~n~ số nguyên ~a_i~.

~q~ dòng tiếp theo, mỗi dòng chứa ~u~ và ~v~.

Dữ liệu ra

Gồm ~q~ dòng, mỗi dòng là độ chênh lệch nhỏ nhất của truy vấn tương ứng.

Giới hạn

~1 \le n, q \le 100000~, ~1 \le a_i \le 10^{9}~.

V? d?

Input

1 1
5
1 1

Output

5