{"problem":{"name":"E. Интеллектуальный отпуск","description":{"content":"Туристическая отрасль в этом сезоне столкнулась с серьёзными сложностями. Добросовестные туроператоры ищут новые рекламные ходы для продажи своих туров. Как известно, наиболее благоприятная для отдыха","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10059E"},"statements":[{"statement_type":"Markdown","content":"Туристическая отрасль в этом сезоне столкнулась с серьёзными сложностями. Добросовестные туроператоры ищут новые рекламные ходы для продажи своих туров. Как известно, наиболее благоприятная для отдыха погода меняется плавно, причём не только от одного дня к другому, но и в течение суток.\n\nДля большинства туристических направлений есть многолетние посекундные результаты измерений различных климатических параметров, например, температуры или влажности. У каждого человека своё понимание того, насколько различными могут быть подобные значения во время отпуска, но всех интересуют непрерывные туры как можно большей продолжительности.\n\nПусть мы зафиксировали туристическое направление и некоторый климатический параметр. Будем называть #cf_span(class=[tex-font-style-underline], body=[изменчивостью]) тура разницу между максимальным и минимальным значением выбранного параметра за всё время поездки. Для каждого туриста известно максимальное приемлемое значение изменчивости ki.\n\nДаны результаты измерений некоторого климатического параметра на одном из курортов и значения ki для нескольких туристов. Требуется для каждого из них определить максимальный диапазон, подходящий для отпуска.\n\nВ первой строке входного файла находится целое число N (1 ≤ N ≤ 600 000) — количество сделанных измерений. Во второй строке — N целых чисел, по модулю не превосходящих 109 — данные посекундных измерений.\n\nВ третьей строке входного файла находится число M (1 ≤ M ≤ 100) — количество туристов, для которых необходимо найти оптимальный диапазон. В четвёртой строке — M целых чисел k1, k2, ..., kM (0 ≤ ki ≤ 109) — максимальная возможная разница между выбранным климатическим параметром в непрерывном диапазоне дней для каждого из туристов. \n\nВ выходной файл для каждого из M запросов в отдельной строке выведите два числа: номер первого измерения диапазона и номер последнего измерения, входящего в диапазон. Нумерация измерений ведётся с единицы. Если для некоторого туриста существует несколько подходящих диапазонов максимальной длины, выведите границы любого из них.\n\n## Входные Данные\n\nВ первой строке входного файла находится целое число N (1 ≤ N ≤ 600 000) — количество сделанных измерений. Во второй строке — N целых чисел, по модулю не превосходящих 109 — данные посекундных измерений.В третьей строке входного файла находится число M (1 ≤ M ≤ 100) — количество туристов, для которых необходимо найти оптимальный диапазон. В четвёртой строке — M целых чисел k1, k2, ..., kM (0 ≤ ki ≤ 109) — максимальная возможная разница между выбранным климатическим параметром в непрерывном диапазоне дней для каждого из туристов. \n\n## Выходные Данные\n\nВ выходной файл для каждого из M запросов в отдельной строке выведите два числа: номер первого измерения диапазона и номер последнего измерения, входящего в диапазон. Нумерация измерений ведётся с единицы. Если для некоторого туриста существует несколько подходящих диапазонов максимальной длины, выведите границы любого из них.\n\n## Примеры\n\nВходные данные710 1 10 12 11 1 1122 1Выходные данные3 54 5\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of measurements.  \nLet $ A = (a_1, a_2, \\dots, a_N) $ be a sequence of integers, where $ |a_i| \\leq 10^9 $ for all $ i \\in \\{1, \\dots, N\\} $.  \nLet $ M \\in \\mathbb{Z}^+ $ be the number of tourists.  \nLet $ K = (k_1, k_2, \\dots, k_M) $ be a sequence of non-negative integers, where $ k_j \\in [0, 10^9] $ for all $ j \\in \\{1, \\dots, M\\} $.\n\n**Constraints**  \n1. $ 1 \\leq N \\leq 600{,}000 $  \n2. $ 1 \\leq M \\leq 100 $  \n3. $ |a_i| \\leq 10^9 $ for all $ i \\in \\{1, \\dots, N\\} $  \n4. $ 0 \\leq k_j \\leq 10^9 $ for all $ j \\in \\{1, \\dots, M\\} $\n\n**Objective**  \nFor each tourist $ j \\in \\{1, \\dots, M\\} $, find a contiguous subarray $ A[i..l] = (a_i, a_{i+1}, \\dots, a_l) $, with $ 1 \\leq i \\leq l \\leq N $, such that:  \n$$\n\\max_{p \\in [i,l]} a_p - \\min_{p \\in [i,l]} a_p \\leq k_j\n$$  \nand the length $ l - i + 1 $ is maximized.  \n\nOutput the pair $ (i, l) $ — the 1-based indices of the first and last measurement of such a subarray.  \nIf multiple such subarrays exist, output any one.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10059E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}