E. Циклические скобки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$S$$$, состоящая из $$$k$$$ видов пар скобок. Каждая скобка имеет вид $$$t$$$ — целое число, такое что $$$1 \leq |t| \leq k$$$. Если скобка имеет вид $$$t$$$, то

  • Если $$$t$$$ > 0, то это открывающая скобка типа $$$t$$$.
  • Если $$$t$$$ < 0, то это закрывающая скобка типа $$$-t$$$.

Таким образом, всего существует $$$k$$$ типов пар скобок.

Напомним определение правильной скобочной последовательности:

  • Пустая последовательность является правильной.
  • Если $$$A$$$ и $$$B$$$ - две правильные скобочные последовательности, то их конкатенация $$$« AB»$$$ тоже является правильной скобочной последовательностью.
  • Если $$$A$$$ - правильная скобочная последовательность, $$$c \ (1\leq c \leq k)$$$ — некоторый тип скобок, то последовательность $$$«c\ \ A\ \ {-c}»$$$ тоже является правильной.
Циклический сдвиг скобочной последовательности вправо на 1 действует следующим образом: последний элемент последовательности ставится в начало, то есть перед самым первым элементом, а затем удаляется с конца.

Циклический сдвиг скобочной последовательности вправо на $$$m$$$ > 1 эквивалентен $$$m$$$ циклическим сдвигам на 1.

Найдите все такие $$$m \ (0 \leq m \leq |S| - 1) $$$, что при циклическом сдвиге на $$$m$$$ элементов получившаяся скобочная последовательность будет правильной.

Входные данные

В первой строке дано целое число $$$n \ (1 \leq n \leq 1 \ 000 \ 000)$$$ — длина строки.

Во второй строке дана строка $$$s$$$ длиной $$$n$$$ символов — $$$n$$$ целых чисел $$$s_1, \ s_2, \ ..., \ s_n \ (1 \leq |s_i| \leq 10^9)$$$.

Выходные данные

В первой строке выведите количество сдвигов, которые дают правильную скобочную последовательность, в следующей строке выведите сами эти сдвиги в порядке возрастания.

Система оценки
ГруппаБаллыДоп. ограниченияНеобх. группыКомментарий
$$$0$$$$$$0$$$——Тесты из условия
$$$1$$$$$$7$$$$$$n \leq 500$$$, $$$k = 1$$$—Каждый тест
$$$2$$$$$$10$$$$$$n \leq 5000$$$, $$$k = 1$$$—Каждый тест
$$$3$$$$$$20$$$$$$k = 1$$$—Каждый тест
$$$4$$$$$$26$$$$$$n \leq 5000$$$, $$$k \leq 10^9$$$—Каждый тест
$$$5$$$$$$37$$$$$$k \leq 10^9$$$—Каждый тест
Примеры
Входные данные
4
1 2 -1 -2
Выходные данные
0
Входные данные
8
-2 2 2 -2 1 -1 -2 2
Выходные данные
2
1 7
Входные данные
8
-1 -3 4 -4 -5 5 3 1
Выходные данные
1
3
Примечание

В первом тестовом примере все циклические сдвиги строки это:

  • 1 2 -1 -2
  • -2 1 2 -1
  • -1 -2 1 2
  • 2 -1 -2 1

Правильной скобочной последовательности среди них нет.

Во втором тестовом примере циклические сдвиги это 1 и 7:

  • 2 -2 2 2 -2 1 -1 -2
  • 2 2 -2 1 -1 -2 2 -2

Можно заметить, что других сдвигов, которые дают правильную скобочную последовательность нет.