Вам дан массив $$$a$$$ длины $$$n$$$. Тройка чисел $$$(x, y, z)$$$ называется красивой, если выполняются условия: $$$x$$$ делится на $$$y$$$ без остатка, $$$y$$$ делится на $$$z$$$ без остатка, и $$$x \gt y \gt z$$$.
Даны $$$q$$$ запросов вида $$$(l, r)$$$. Необходимо для каждого запроса найти такие индексы $$$i \lt j \lt k$$$ в массиве $$$a$$$, что тройка $$$(a_i, a_j, a_k)$$$ является красивой и $$$l \leq i \lt j \lt k \leq r$$$. Из всех таких троек выбрать ту, которая максимизирует значение $$$n^2 \cdot a_i + n \cdot a_j + a_k$$$. Если существует несколько троек с максимальным значением, выбрать лексикографически минимальную тройку $$$(i, j, k)$$$.
Первая строка содержит одно целое число $$$n$$$ — длину массива $$$a$$$ ($$$1 \leq n \leq 10^{5}$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — элементы массива $$$a$$$.
Третья строка содержит одно целое число $$$q$$$ ($$$1 \leq q \leq 10^{5}$$$) — количество запросов.
Далее следуют $$$q$$$ строк, каждая из которых содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) — границы текущего запроса.
Для каждого запроса выведите тройку $$$(i, j, k)$$$, которая является ответом на запрос, если такая тройка найдена. Если тройка $$$(i, j, k)$$$ не была найдена, выведите $$$-1$$$.
8 8 4 2 1 4 2 8 1 4 2 4 2 7 1 7 3 5
2 3 4 2 3 4 1 2 3 -1
| Almaty Code Cup 2024 |
|---|
| Закончено |
