Задача 4: Измерения температуры В результате измерения были получены...

Задача 4: Измерения температуры
В результате измерения были получены среднедневные температуры за N последовательных дней (1 ? N ? 10^7)
Иннокентий решил найти максимальную температуру на всех последовательных интервалах длины K (1 ? K ? 10^4, K ? N). То есть на отрезках [0..K-1], [1..K], [2..K+1] и т.д.
.
Результаты поисков не понравились Иннокентию, поэтому он решил расширить слева и справа каждый i-й отрезок на li, ri соответственно. Считайте, что если при этом происходит выход за границы исходной последовательности, то числа там -inf.
На стандартном потоке вводится число N и N чисел задаюших последовательность измерений. Затем K - длина отрезка поиска, затем N-K+1 пары положительных чисел не больших 1000 и не больших K - li, ri соответственно.
Для каждого из N-K+1 отрезков длины K c соответствующими расширениями выведите максимум на них
Примеры
Входные данные
10
1 2 3 1 3 7 8 5 3 1
3
0 1
1 1
0 1
0 0
0 0
0 0
0 0
1 0
Результат работы
3
3
7
7
8
8
8
8