Bạn được cho mảng \(x\) có \(n\) phần tử (được đánh số \(1, 2, 3, ..., n\)) và \(q\) truy vấn. Bạn có thể thực hiện một thao tác, đó là lấy một phần tử \(x_i\) bất kì và tăng nó lên 1 đơn vị.

Nhiệm vụ của bạn là với mỗi truy vấn \(q\), hãy tính xem bạn cần thực hiện thao tác trên bao nhiêu lần để đoạn con [\(a, b\)] là đoạn con không giảm.

(Một đoạn con không giảm là một đoạn con mà phần tử đứng trước luôn lớn hơn hoặc bằng phần tử đứng sau nó)

Input:

Dòng đầu gồm 2 số \(n\) và \(q\), lần lượt là số lượng phần tử của mảng \(a\) và số lượng truy vấn,

Dòng thứ 2 gồm \(n\) số \(x_1, x_2, .. x_n\), là các phần tử của mảng \(x\),

\(q\) dòng cuối, mỗi dòng là một truy vấn có dạng \(a, b\).

Ouput:

Với mỗi truy vấn, in ra số thao tác cần ít nhất để đoạn con [\(a, b\)] là một đoạn con không giảm.

Constraints:

\(1\) ≤ \(n\), \(q\) ≤ \(2 .10 ^ 5\)

\(1\) ≤ \(x_i\) ≤ \(10^9\)

\(1\) ≤ \(a, b\) ≤ \(n\)

Example(s):

Input:

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

Output:

2
0
14