Cho mảng ~A~ gồm ~n~ phần tử ~A_1, A_2, ..., A_n~. Ta gọi độ thú vị của mảng ~A~ là giá trị ~x~ lớn nhất sao cho ~x~ nhỏ hơn hoặc bằng số lượng phần tử lớn hơn hoặc bằng ~x~. Hay nói cách khác:

$$x \le \sum_i^n(~A_i \ge x~). $$

Biểu thức (~A_i \ge x~) là ~1~ khi ~A_i \ge x~, ngược lại là ~0.~

Bạn hãy trả lời ~q~ truy vấn, mỗi truy vấn có dạng ~l_i, r_i~: Độ thú vị mảng con liên tiếp của A trong đoạn [~l_i, r_i~]

Input

Dòng đầu tiên gồm 2 số n và q (~ 2 \le n, q \le 200000 ~) - số phần tử trong mảng A và số truy vấn.

Dòng thứ hai gồm n số nguyên ~A_1, A_2, ..., A_n~ (~1 \le A_i \le 200000~)

Tiếp theo là ~q~ dòng. Mỗi dòng gồm hai số nguyên ~l_i, r_i~ (~1 \le l_i, r_i \le n~)

Output

In ra q dòng. Mỗi dòng là kết quả truy vấn tương ứng.

Subtask 1: 30% số điểm (~1 \le n, q \le 500 ~)

Subtask 2: 35% số điểm (~100 \le n, q \le 50000 ~)

Subtask 2: 35% số điểm (~50000 \le n, q \le 200000 ~)

Examples

Input

7 4
3 2 1 4 5 2 4 
1 7
4 5
4 7
2 3 

Output

3
2 
3 
1 

*Giải thích: *

Truy vấn thứ 1: trong đoạn [1, 7] có độ thú vị là 3 vì có 3<=cnt[~A_i~ >= 3] là 4, trong khi độ thú vị là 4 không hợp lệ vì có 4>cnt[~A_i~ >= 4] là 3.

Truy vấn thứ 2: trong đoạn [4, 5] có độ thú vị là 2 vì 2<=cnt[~A_i~ >= 2] là 2.