Cho dãy số nguyên \(a_1, a_2, \ldots, a_n\), và \(q\) truy vấn tìm \(\max(a_l, a_{l + 1}, \ldots, a_{r})\).

Input

• Dòng đầu chứa số nguyên dương \(n, q\) \((n, q \le 2\cdot 10^5)\).
• Dòng thứ hai chứa \(n\) số \(a_1, a_2, ..., a_n\) \((1\le a_i\le n)\).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số \(l, r\) \((1\le l\le r\le n)\) mô tả các truy vấn.

Output

• Ghi ra tổng giá trị kết quả của các truy vấn.

Example

5 4
3 4 2 1 3
1 3
3 5
2 3
1 4

15