Задача №114687. Поеду домой
На третьем месяце дистанционного обучения студентке Насте стало скучно, и она решила поехать домой к себе в родной город на пару недель с целью развеяться. Чтобы ей было веселее в дороге, её друг подарил ей массив целых чисел \(a\).
Шел пятый час поездки, и Настя вспомнила про подарок. Чтобы развлечь себя, она решила проверить, можно ли выбрать четыре различных индекса \(x, y, z, w\) таких, что \(a_x + a_y = a_z + a_w\).
Занявшись этим делом, Настя не заметила, как прошло время, и её поезд уже пришел на станцию назначения. Она не успела закончить проверку, но всё ещё хочет узнать истину. Сможете ей помочь?
Первая строка содержит целое число \(n\) (\(4 \leq n \leq 200\,000\)) — количество чисел в массиве.
Вторая строка содержит целые числа \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 5 \cdot 10^6\)).
На первой строке выведите « YES », если четыре таких индекса существуют, и « NO » иначе.
Если такие индексы существуют, выведите в следующей строке \(x\), \(y\), \(z\) и \(w\) (\(1 \le x, y, z, w \le n\)).
Если возможных ответов несколько, выведите любой.
В первом примере \(a_2 + a_3 = 1 + 5 = 2 + 4 = a_1 + a_6\). Обратите внимание, что ответ 2 3 4 6 также подходит.
Во втором примере нельзя выбрать четыре таких индекса. Ответ 1 2 2 3 не подходит, потому что в нем не все индексы различны, хоть и \(a_1 + a_2 = 1 + 3 = 3 + 1 = a_2 + a_3\)
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех предыдущих групп.
| Дополнительные ограничения | |||
| Группа | Баллы | \(n\) | Комментарий |
| 0 | 0 | – | Тесты из условия. |
| 1 | 30 | \(n \le 60\) | |
| 2 | 30 | \(n \le 600\) | |
| 3 | 40 | – |
6 2 1 5 2 7 4
YES 2 3 1 6
5 1 3 1 9 20
NO