Cho dãy số \(n\) nguyên dương \(a_1, a_2, a_3, \dots,a_n\). Gọi \(m(l, r)\) là vị trí của giá trị nhỏ nhất trong đoạn \(a_l, a_{l+1}, \dots, a_r\) (nếu có nhiều số nhỏ nhất thì chọn số có vị trí lớn nhất).
Ta định nghĩa \(f(l, r)\) như sau:

   \(f(l, r) = f(l, m(l, r) - 1) + f(m(l, r) + 1, r) +(r - l + 1)\) nếu \(l \leq r\).
   \(f(l, r) = 0\) nếu \(l > r\).

Có \(q\) truy vấn, mỗi truy vấn gồm hai số nguyên dương \(l, r (1 \leq l \leq r \leq n)\). Với mỗi truy vấn cần tính giá trị \(f(l, r)\).

Input

• Dòng đầu gồm 2 số nguyên dương \(n, q\) \((n, q \leq 10^{6})\).
• Dòng tiếp theo gồm dãy \(a_1, a_2, a_3, \dots, a_n\) \((1 \leq a_i \leq 10^9)\).
• \(q\) dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương \(l, r\) \((1 \leq l \leq r \leq n)\).

Output

• \(q\) dòng là kết quả của các giá trị \(f(l, r)\) tương ứng.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, q \leq 500\)
• Subtask \(2\) (\(30\%\) số điểm): \(n, q \leq 5000\)
• Subtask \(3\) (\(40\%\) số điểm): \(n, q \leq 10^6\)

Example

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

1
6
8
5
1