G. Интеллектуальный отпуск

Даны посекундные результаты измерений климатического параметра. Изменчивостью тура называется разница между максимальным и минимальным значением параметра за всё время поездки.

Для каждого туриста известно максимальное приемлемое значение изменчивости $k_i$. Требуется для каждого определить максимальный по длине диапазон, подходящий для отпуска.

В первой строке целое число $N$ ($1 \le N \le 600\,000$) — количество измерений. Во второй — $N$ целых чисел, по модулю не превосходящих $10^9$. В третьей строке число $M$ ($1 \le M \le 100$) — количество туристов. В четвёртой — $M$ целых чисел $k_1, \ldots, k_M$ ($0 \le k_i \le 10^9$).

Для каждого из $M$ запросов в отдельной строке выведите два числа: номер первого и номер последнего измерения диапазона. Нумерация с единицы. Если подходящих диапазонов максимальной длины несколько, выведите границы любого.