Вам задан массив, состоящий из n целых чисел a₁, a₂, ..., a_n. Также задано m запросов, i-ый запрос описывается двумя целыми числами l_i, r_i. Числа l_i, r_i обозначают подотрезок исходного массива, то есть последовательность чисел a_li, a_li + 1, a_li + 2, ..., a_ri. Для каждого запроса нужно проверить, является ли соответствующий ему подотрезок лесенкой.

Лесенкой назовем последовательность целых чисел b₁, b₂, ..., b_k такую, что сначала она не убывает, а затем не возрастает. Другими словами, существует такое целое число x (1 ≤ x ≤ k), что выполняется неравенство: b₁ ≤ b₂ ≤ ... ≤ b_x ≥ b_x + 1 ≥ b_x + 2... ≥ b_k. Обратите внимание, что неубывающая и невозрастающая последовательности также считаются лесенками.