Дана последовательность $A_1, A_2, \ldots, A_N$ длины $N$. Напишите программу, которая обрабатывает следующие запросы:

• m k: Среди подпоследовательностей $A_1, A_2, \ldots, A_m$ найдите максимальную длину подпоследовательности, длина наибольшей возрастающей подпоследовательности которой не превышает $k$. ($1 \le k \le m \le N$)

Входные данные

Первая строка содержит длину последовательности $N$ и количество запросов $Q$. ($1 \le N \le 50{,}000$, $1 \le Q \le 200{,}000$)

Вторая строка содержит $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 50{,}000$)

Следующие $Q$ строк содержат по одному запросу в описанном выше формате.

Выходные данные

Для каждого запроса выведите ответ на отдельной строке.

Примеры

Ввод 1

11 6
9 6 3 1 5 12 8 4 2 2 2
5 1
7 2
9 1
9 2
11 1
11 11

Вывод 1

4
6
5
8
7
11