Cho một dãy \(N\) số nguyên dương \(A_1,A_2,…,A_N\). Một thao tác thay đổi là việc chọn một phần tử \(a_i (1\leq i \leq N)\) và thay thế \(A_i=A_i+1\).

Yêu cầu: Bạn cần trả lời \(q\) truy vấn. Mỗi truy vấn cho bạn một dãy con liên tiếp trong đoạn từ \(l\rightarrow r\) và yêu cầu tính xem số lượng thao tác thay đổi tối thiểu để cho dãy con đã cho thành dãy không giảm.

Input

• Dòng đầu chứa hai số nguyên dương \(N,q\) \((1\leq N,q \leq 2 \times 10^5)\);
• Dòng tiếp theo gồm \(N\) số nguyên dương \(A_1,A_2,…,A_n\) \((A_i\leq 10^9)\).
• \(q\) dòng cuối cùng, mỗi dòng gồm 2 số nguyên dương \(l, r\) \((1\leq l \leq r \leq n)\) biểu thị cho dãy con từ \(l\) đến \(r\).

Output

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

Example

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

2
0
14