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

Пока длина массива больше единицы, выполняется следующая операция: выбирается произвольный отрезок массива длины 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}]\). Для всех запросов гарантируется, что длина отрезка запроса нечетна.