Tý có một dãy số nguyên dương \(A\) và \(Q\) truy vấn. Mỗi truy vấn gồm hai số \(L, R\), yêu cầu đếm số lượng đoạn con \([l, r]\) thỏa mãn \(L \le l \le r \le R\) và giá trị nhỏ nhất của đoạn \([l, r]\) đúng bằng \(A_L\) (phần tử đầu tiên của đoạn con).

Ràng buộc

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L, R\) (\(1 \le L \le R \le N\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra số lượng đoạn con thỏa mãn.

Ví dụ

Input:

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

Output:

2
3
1