| Codeforces Round 276 (Div. 1) |
|---|
| Закончено |
Бизон-Чемпион недавно закончил покраску своего забора. Забор представляет из себя последовательность из n досок ширины 1 метр и произвольной высоты. i-я доска имеет высоту hi метров. Соседние доски следуют без зазора.
После покраски Бизон-чемпион решил разместить на заборе объявление о его продаже. Объявление будет выполнено на листе бумаги прямоугольного размера и расположено на заборе так, что боковые стороны листа параллельны доскам забора, и края листа совмещены с краями некоторых досок. Бизон-Чемпион ввел для себя следующие ограничения на размещение объявления:
- Ширина объявления после размещения должна быть ровно w метров.
- Объявление должно целиком находиться на участке забора с 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
Забор, описанный в примере, выглядит следующим образом:
Ниже приведены возможные расположения объявлений при ответе на запросы.
Расположение объявления при ответе на первый запрос. 
Расположение объявления при ответе на второй запрос. 
Расположение объявления при ответе на третий запрос. 
