Ở ngôi làng nọ có một con đường thẳng và dài rất đẹp. Tuy nhiên vào mùa thu, đông, cây cối 2 bên đường đã rụng lá rất nhiều và ảnh hưởng đến việc đi lại. Trưởng làng đã bố trí $N$ người dân dọn lá tại các điểm khác nhau của con đường. Nhưng vì tuổi tác cao nên trí nhớ trưởng làng không còn tốt nữa, bạn cần giúp trưởng làng trả lời $Q$ câu hỏi, mỗi câu hỏi yêu cầu cho biết số người dân dọn lá trong một đoạn đường cho trước.

Input

Dòng đầu chứa $2$ số $N$ và $Q$ $(1\le N,Q\le {10}^6)$.

Dòng thứ $2$ chứa $N$ số nguyên phân biệt $x_1,x_2,...,x_N$, mỗi số thuộc đoạn $[1,{10}^6]$ cho biết vị trí một người dân.

Mỗi dòng trong $Q$ dòng tiếp theo chứa $2$ số nguyên $A$ và $B$ $(0\le A\le B\le {10}^6)$.

Output

Đưa ra $Q$ dòng, mỗi dòng là một số nguyên trả lời cho câu hỏi tương ứng.

Example

Sample Input

4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10

Sample Output

2
2
3
4
1
0

Subtask

$50\mathrm{\%}$ số test có $N,Q\le {10}^2$.

$50\mathrm{\%}$ số test có $N,Q\le {10}^6$.