Дан массив \(a_1, \ldots, a_n\) из \(n\) положительных целых чисел. За одну операцию можно выбрать индекс \(i\), удовлетворяющий \(a_i = i\), и удалить \(a_i\) из массива (после удаления остальные части массива соединяются).
Вес \(a\) определяется как максимальное количество элементов, которые можно удалить.
Вы должны ответить на \(q\) независимых запросов \((x, y)\): после замены первых \(x\) элементов \(a\) и последних \(y\) элементов \(a\) на \(n+1\) (делая их удаление невозможным), чему будет равен вес \(a\)?
Выходные данные
Выведите \(q\) строк, \(i\)-я строка должна содержать единственное целое число — ответ на \(i\)-й запрос.
Примечание
Объяснение первого запроса:
После того, как первые \(x = 3\) и последние \(y = 1\) элементов стало невозможно удалить, \(a\) становится равным \([\times, \times, \times, 9, 5, 4, 6, 5, 7, 8, 3, 11, \times]\) (для наглядности мы представляем \(14\) как \(\times\)).
Вот стратегия, которая удаляет \(5\) элементов (удаленный элемент окрашен в красный цвет):
- \([\times, \times, \times, 9, \color{red}{5}, 4, 6, 5, 7, 8, 3, 11, \times]\)
- \([\times, \times, \times, 9, 4, 6, 5, 7, 8, 3, \color{red}{11}, \times]\)
- \([\times, \times, \times, 9, 4, \color{red}{6}, 5, 7, 8, 3, \times]\)
- \([\times, \times, \times, 9, 4, 5, 7, \color{red}{8}, 3, \times]\)
- \([\times, \times, \times, 9, 4, 5, \color{red}{7}, 3, \times]\)
- \([\times, \times, \times, 9, 4, 5, 3, \times]\) (конечное состояние)
Невозможно удалить более \(5\) элементов, поэтому вес составляет \(5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
13 5
2 2 3 9 5 4 6 5 7 8 3 11 13
3 1
0 0
2 4
5 0
0 12
|
5
11
6
1
0
|
|
2
|
5 2
1 4 1 2 4
0 0
1 0
|
2
0
|