На курсе по математической статистике Боб придумал новый способ вычисления среднего для массивов, содержащих нечетное число элементов.

Пока длина массива больше единицы, выполняется следующая операция: выбирается произвольный отрезок массива длины 3 с границами $$$l$$$ и $$$r = l + 2$$$, вычисляется медиана этих трех элементов и затем эти элементы заменяются на один элемент, равный медиане.

Напомним, что медианой массива из трех элементов называется второй по возрастанию элемент данного массива. Например, медиана массива $$$[1, 5, 4]$$$ равна $$$4$$$, а медиана массива $$$[2, 2, 2]$$$ равна $$$2$$$.

Рассмотрим один из способов вычисления среднего по Бобу на массиве $$$[4, 1, 3, 2, 5]$$$. На первом шаге выбираем подотрезок с границами $$$l = 2$$$, $$$r = 4$$$. Так как $$$2$$$ является медианой подмассива $$$[1, 3, 2]$$$, то массив преобразуется следующим образом: $$$[4, \textbf{1, 3, 2}, 5] \rightarrow [4, \textbf{2}, 5]$$$. На втором шаге единственный возможный отрезок длины $$$3$$$ имеет границы $$$l = 1$$$, $$$r = 3$$$. Так как $$$4$$$ является медианой подмассива $$$[4, 2, 5]$$$, то $$$[\textbf{4, 2, 5}] \rightarrow [4]$$$.

Боб заметил, что его способ вычисления среднего определен не вполне корректно: в зависимости от выбора отрезков результат вычисления может получиться разным. Чтобы исправить эту ситуацию, Боб решил выбирать отрезки для замены на медиану таким образом, чтобы единственное оставшееся в конце число было максимальным возможным. Именно это число Боб называет средним по Бобу для данного массива.

Для массива $$$a$$$ из $$$n$$$ элементов вам требуется ответить на $$$q$$$ запросов, $$$j$$$-й из которых характеризуется границами $$$L_j$$$ и $$$R_j$$$.

Ответом на $$$i$$$-й запрос является среднее по Бобу отрезка исходного массива $$$[a_{L_j}, a_{L_j + 1}, \ldots a_{R_j}]$$$. Для всех запросов гарантируется, что длина отрезка запроса нечетна.