Có n ổ kiến x1, x2, ..., xn, nằm trên đoạn [−10^9, 10^9]. Tuy là các ổ kiến này riêng biệt nhau nhưng lại có cùng một vua kiến. Vua kiến đang có Q dự định là gộp tất cả các ổ kiến nằm trong đoạn [Li, Ri] thành 1 ổ tại một vị trí nào đó (nếu ban đầu vị trí đó không có ổ kiến nào, vua kiến sẽ cho lính lác xây một ổ mới). Tổng thời gian để tất cả chú kiến có mặt trong ổ xi di chuyển tới một vị trí p là |xi − p|. Với mỗi dự định vua kiến thắc mắc là có bao nhiêu vị trí mà tổng thời gian di chuyển của các chú kiến là ít nhất.

Input:

• Dòng 1 chứa hai số nguyên n, q là số lượng tổ kiến và số lượng dự định của kiến vua (1 ≤ n, q ≤ 2* 10^5).

• Dòng tiếp theo chứa n số nguyên −10^9 ≤ x1 ≤ x2 ≤ ... ≤ xn ≤ 10^9, là vị trí các tổ kiến.

• q dòng tiếp theo mỗi dòng chứa hai số nguyên L, R (1 ≤ L ≤ R ≤ n).

Output:

Với mỗi dự định của nhà vua in ra mỗi dòng một số nguyên là số lượng vị trí thoã mãn.

Sample Input

6 3
-5 -3 0 3 5 5
1 6
1 5
2 4

Sample Output

4
1
1