Задача №112689. Интеллектуальный отпуск
Туристическая отрасль в этом сезоне столкнулась с серьёзными сложностями. Добросовестные туроператоры ищут новые рекламные ходы для продажи своих туров. Как известно, наиболее благоприятная для отдыха погода меняется плавно, причём не только от одного дня к другому, но и в течение суток.
Для большинства туристических направлений есть многолетние посекундные результаты измерений различных климатических параметров, например, температуры или влажности. У каждого человека своё понимание того, насколько различными могут быть подобные значения во время отпуска, но всех интересуют непрерывные туры как можно большей продолжительности.
Пусть мы зафиксировали туристическое направление и некоторый климатический параметр. Будем называть изменчивостью тура разницу между максимальным и минимальным значением выбранного параметра за всё время поездки. Для каждого туриста известно максимальное приемлемое значение изменчивости k i .
Даны результаты измерений некоторого климатического параметра на одном из курортов и значения k i для нескольких туристов. Требуется для каждого из них определить максимальный диапазон, подходящий для отпуска.
В первой строке входного файла находится целое число N ( 1 ≤ N ≤ 600 000 ) "— количество сделанных измерений. Во второй строке "— N целых чисел, по модулю не превосходящих 10 9 — данные посекундных измерений.
В третьей строке входного файла находится число M ( 1 ≤ M ≤ 100 ) "— количество туристов, для которых необходимо найти оптимальный диапазон. В четвёртой строке "— M целых чисел k 1 , k 2 , ..., k M ( 0 ≤ k i ≤ 10 9 ) "— максимальная возможная разница между выбранным климатическим параметром в непрерывном диапазоне дней для каждого из туристов.
В выходной файл для каждого из M запросов в отдельной строке выведите два числа: номер первого измерения диапазона и номер последнего измерения, входящего в диапазон. Нумерация измерений ведётся с единицы. Если для некоторого туриста существует несколько подходящих диапазонов максимальной длины, выведите границы любого из них.
7 10 1 10 12 11 1 11 2 2 1
3 5 4 5