На самой большой улице города Есик растут n деревьев в один ряд. Высота i-го дерева слева равна aᵢ. В конце каждой минуты происходит следующая трансформация:
• Если хотя бы один сосед дерева i на данный момент выше него, дерево i растет на 1 единицу высоты. Более формально, должно выполняться хотя бы одно из условий aᵢ₋₁ > aᵢ или aᵢ₊₁ > aᵢ. Здесь мы полагаем, что a₀ = aₙ₊₁ = 0.
Отметим, что трансформация происходит одновременно для всех деревьев. Например, если высоты деревьев на данный момент равны [3,3,4,2,2], на следующей минуте высоты будут равны [3,4,4,3,2].
Изначальные высоты деревьев соответствуют 0-й минуте. Вам нужно ответить на q независимых запросов следующего типа.
• Какая высота у x-го дерева в начале t-й минуты?
Формат входных данных
Первая строка содержит два целых числа n и q (2 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵) — количество деревьев и количество запросов.
Вторая строка содержит n целых чисел a₁,...,aₙ (1 ≤ aᵢ ≤ 10¹⁸, для всех i, где 1 ≤ i ≤ n) — изначальные высоты всех деревьев.
Следующие q строк содержат пары (xᵢ,tᵢ) (1 ≤ xᵢ ≤ n, 0 ≤ tᵢ ≤ 10¹⁸) — описания запросов.
Формат выходных данных
Выведите q чисел — ответы на все запросы в порядке их появления во входных данных.