Как найти самый длинный непрерывный фрагмент в массиве a1,a2...aN, сумма элементов которого делится на 3? Входные

Входные данные для задачи содержат число N, которое ограничено значением ≤ 100000. Затем следуют N чисел, элементы массива a1, a2, ..., aN, которые не превышают по модулю 10^9.

Итак, у нас есть массив из N элементов, и нам нужно найти самый длинный непрерывный фрагмент этого массива, сумма элементов которого делится на 3. Если таких фрагментов несколько, мы должны вывести фрагмент с наименьшим индексом начала. Если такого фрагмента не существует, мы должны вывести -1.

Давайте рассмотрим пример для лучшего понимания:

Предположим, у нас есть следующий массив a: [5, 7, 1, 8, 2, 6, 4, 9].

Нам необходимо найти самый длинный непрерывный фрагмент сумма элементов которого делится на 3.

1. Начнем с нахождения суммы всех элементов в массиве - это поможет нам в дальнейшем. В данном случае, сумма всех элементов равна 42.

2. Теперь проверим, делится ли эта сумма на 3. В данном случае, сумма 42 делится на 3 без остатка.

3. Начнем поиск самого длинного непрерывного фрагмента, сумма элементов которого делится на 3. Рассмотрим все возможные фрагменты, начиная с первого элемента и заканчивая последним:

- [5] - сумма: 5, не делится на 3.
- [5, 7] - сумма: 12, делится на 3.
- [5, 7, 1] - сумма: 13, не делится на 3.
- [5, 7, 1, 8] - сумма: 21, не делится на 3.
- [5, 7, 1, 8, 2] - сумма: 23, не делится на 3.
- [5, 7, 1, 8, 2, 6] - сумма: 29, не делится на 3.
- [5, 7, 1, 8, 2, 6, 4] - сумма: 33, делится на 3.
- [5, 7, 1, 8, 2, 6, 4, 9] - сумма: 42, делится на 3.

4. Мы видим два фрагмента, сумма элементов которых делится на 3, а именно [5, 7] и [5, 7, 1, 8, 2, 6, 4, 9]. Но нам нужно выбрать фрагмент с наименьшим индексом начала, поэтому ответом будет [5, 7], с индексами начала и конца: 1, 2.

В случае, если ни один фрагмент не удовлетворяет условиям задачи, мы должны вывести -1.