E. Объявление на заборе
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Бизон-Чемпион недавно закончил покраску своего забора. Забор представляет из себя последовательность из n досок ширины 1 метр и произвольной высоты. i-я доска имеет высоту hi метров. Соседние доски следуют без зазора.

После покраски Бизон-чемпион решил разместить на заборе объявление о его продаже. Объявление будет выполнено на листе бумаги прямоугольного размера и расположено на заборе так, что боковые стороны листа параллельны доскам забора, и края листа совмещены с краями некоторых досок. Бизон-Чемпион ввел для себя следующие ограничения на размещение объявления:

  1. Ширина объявления после размещения должна быть ровно w метров.
  2. Объявление должно целиком находиться на участке забора с l-й по r-ю доски включительно (в том числе, нельзя выходить за пределы забора по вертикали).

Объявление будет красочным, поэтому Бизон-чемпион хочет, чтобы высота объявления была как можно больше.

Вам дано описание забора и несколько запросов на размещение объявления. Для каждого запроса выведите максимальную возможную высоту объявления, которое можно разместить на соответствующем участке забора при заданной фиксированной ширине объявления.

Входные данные

В первой строке ввода содержится целое число n — количество досок в заборе (1 ≤ n ≤ 105).

Во второй строке записаны n целых чисел hi, разделенных пробелом — высоты досок (1 ≤ hi ≤ 109).

В третьей строке содержится целое число m — количество запросов (1 ≤ m ≤ 105).

В последующих m строках идет описание запросов, каждый из которых представлен тремя целыми числами l, r и w (1 ≤ l ≤ r ≤ n, 1 ≤ w ≤ r - l + 1) — соответственно границы участка забора и ширина объявления.

Выходные данные

На каждый запрос выведите ответ в отдельной строке — максимальную высоту объявления, которую можно достичь на соответствующем участке забора при соблюдении всех условий.

Примеры
Входные данные
5
1 2 2 3 3
3
2 5 3
2 5 2
1 5 5
Выходные данные
2
3
1
Примечание

Забор, описанный в примере, выглядит следующим образом:

Ниже приведены возможные расположения объявлений при ответе на запросы.

Расположение объявления при ответе на первый запрос.
Расположение объявления при ответе на второй запрос.
Расположение объявления при ответе на третий запрос.