Задача: Capybara. Канатная дорога
Побывав недавно в лесу, Вася решил построить на деревьях канатную дорогу. Он хочет, чтобы дорога была как можно более длинной, но он плохо помнит высоты деревьев в лесу. К счастью, он уверен, что правильно помнит высоты всех деревьев, кроме, возможно, одного из них.
Известно, что лес состоит из n деревьев, стоящих в ряд и пронумерованных слева направо числами от 1 до n. Высота i-го дерева, по воспоминаниям Васи, равна hi. Канатная дорога длины k должна опираться на k (1 <= k <= n) деревьев i1, i2, . . . , ik (i1 < i2 < . . . < ik), таких что их высота возрастает, то есть, hi1 < hi2 < . . . < hik.
Петя тоже был в лесу, и у него есть q предположений о том, где именно ошибается Вася. Его i-е предположение задаётся числами ai и bi , означающими, что, по мнению Пети, высота дерева
с номером ai на самом деле равна bi . Обратите внимание, Петины предположения независимы между собой.
Ваша задача состоит в том, чтобы для каждого предположения Пети найти максимальную длину канатной дороги, которую можно построить с опорой на эти деревья.
Отметим, что в рамках данной задачи длиной дороги Вася считает количество опорных деревьев в ней.
Формат входных данных
Первая строка входных данных содержит два числа n и m (1 <= n, m <= 400 000) — количество деревьев в лесу и количество предположений Пети соответственно.
В следующей строке содержатся n целых чисел hi (1 <= hi <= 109 ) — высоты деревьев по предположению Васи.
Каждая из следующих m строк содержит по два целых числа ai и bi (1 <= ai <= n, 1 <= bi <= 109 ).
Формат выходных данных
Для каждого предположения Пети выведите в отдельной строке одно число — максимальную длину канатной дороги.
|
Ввод |
Вывод |
4 4
1 2 3 4
1 1
1 4
4 3
4 5 |
4
3
3
4 |
4 2
1 3 2 6
3 5
2 4 |
4
3 |
Замечание
Рассмотрим первый пример. Первое Петино предположение совпадает с предположением Васи.
Согласно его второму предположению, высоты деревьев были (4, 2, 3, 4), третьему (1, 2, 3, 3), а по четвёртому предположению — (1, 2, 3, 5).
Ваш ответ: