Có ~n~ ổ kiến ~x_1, x_2, ..., x_n~, 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 ~[L_i, R_i]~ thành một ổ 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 xây một ổ mới). Tổng thời gian để tất cả chú kiến có mặt trong ổ ~x_i~ di chuyển tới một vị trí ~p~ là ~|x_i - 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 đầu là 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 \le n, q \le 2.10^5)~.
• Dòng tiếp theo chứa ~n~ số nguyên ~-10^9 \le x_1 \le x_2 \le ... \le x_n \le 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 \le L \le R \le 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.

Samples

Sample Input 1

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

Sample Output 1

4
1
1

Sample Input 2

2 1
-197132 1845
1 2

Sample Output 2

198978

Sample Input 3

3 1
1 2 3
1 3

Sample Output 3

1