AlgoLiga 2018

Bajtłomiej wciąż pracuje w Centrum Meteorologicznych Obserwacji i Symulacji. Wcześniejsze praktyki w innych państwowych instutucjach (Bajtłomiej wcześniej wykonywał prace dla BIOS-u, IBM-u czy IMAP-u) uczyniły z niego jednego z najlepszych programistów w kraju. Tym razem CMOS potrzebuje efektywnego systemu wyznaczania amplitudy temperatury powietrza na podstawie pomiarów prowadzonych w wybranej stacji na Płaskowyżu Północnobajtockim.

System, który zaprojektować ma Bajtłomiej, będzie otrzymywał wyniki cogodzinnych pomiarów temperatury. Na podstawie tych danych, powinien obliczyć amplitudę temperatury we wszystkich okresach o określonej długości (czyli obliczoną dla spójnych fragmentów ciągu pomiarów) i wyznaczyć największą z nich.

Wejście

Najpierw liczba pomiarów n (2 ≤ n ≤ 10000).

W drugiej linii n liczb całowitych t_i oznaczających kolejne wyniki pomiarów (−10⁹ ≤ t_i ≤ 10⁹).

W trzeciej linii liczba zapytań q (1 ≤ q ≤ 5000).

W ostatniej linii q liczb d_i (2 ≤ d_i ≤ n) oznaczających długość okresu. 

Wyjście

Dla każdego zapytania, w osobnej linii maksymalna spośród amplitud obliczonych dla wszystkich ciągów pomiarów o zadanej długości.

Przykład

Wejście:
5
-3 -2 3 0 -4
2
2 3 

Wyjście:
5
7 

Pomoc do przykładu:
W pierwszym zapytaniu mamy brać pod uwagę serie złożone z dwóch liczb. Największa amplituda wynosząca 5 występuje pomiędzy drugim i trzecim pomiarem.
W drugim zapytaniu analizujemy podciągi: (-3,-2,3), (-2,3,0), (3,0,-4). Amplitudy wynoszą odpowiednio: 6,5,7.