Cho mảng \(A\) gồm \(n\) số nguyên. Cho \(q\) truy vấn, mỗi truy vấn là hai số nguyên \(l, r\). Hãy tính:

\(A_l + min(A_l, A_{l+1}) + ... + min(A_l, A_{l+1}, ..., A_r)\).

Dữ liệu vào

• Dòng đầu tiên là hai số nguyên dương \(n, q\).
• Dòng thứ hai là \(n\) số nguyên \(A_i\).
• \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(l, r\).

Dữ liệu ra

Với mỗi truy vấn, in ra đáp án trên một dòng.

Điều kiện:

• \(1 \le n, q \le 10^5\).
• \(1 \le A_i \le 10^9\).
• \(1 \le l \le r \le n\).

Input 1

6 3
5 3 7 2 1 4
2 4
3 6
1 3

Output 1

8
11
11