Cho số nguyên \(n\) và dãy số nguyên dương \(a_1,a_2,…,a_n\). Một thao tác biến đổi là chọn một phần tử trong dãy và tăng giá trị phần tử đó lên 1.

Yêu cầu: Cho \(q\) truy vấn, mỗi truy vấn cho một dãy con trong đoạn từ \(l\) đến \(r\) và cho biết mất ít nhất bao nhiêu phép biến đổi để dãy \(a_l,a_{l+1},…,a_r\) thành dãy không giảm.

Input

• Dòng thứ nhất chứa 2 số \(n,q(1 ≤ n,q ≤ 2.10^5 )\).

• Dòng thứ 2 chứa \(n\) số nguyên dương \(a_1,a_2,…,a_n (a_i≤10^9 )\).

• \(q\) dòng tiếp theo mỗi dòng chứa 2 số nguyên dương \(l,r(1≤l≤r≤n)\) biểu thị cho dãy con từ \(l\) đến \(r\).

Output

• In ra \(q\) dòng, mỗi dòng chứa số nguyên không âm là kết quả của truy vấn tương ứng.

Sample Input

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

Sample Output

2
0
14