У вас есть строка $$$s$$$, состоящая из строчных букв латинского алфавита.
Вам нужно разделить эту строку на подстроки, удовлетворяющие следующим требованиям:
Таким образом, если мы склеим в том же порядке все получившиеся подстроки, то получим исходную строку $$$s$$$.
Подстрока строки $$$s$$$ — это непустая последовательность подряд идущих букв строки $$$s$$$.
Например, строку aadddzxxz можно разделить на подстроки aa, ddd и zxxz.
Определите максимальное количество подстрок, на которые можно разделить строку $$$s$$$, а также размеры каждой из этих подстрок. Если разделить строку $$$s$$$ описанным образом невозможно, сообщите об этом.
В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 4 \cdot 10^5$$$) — длина строки $$$s$$$.
Во второй строке следует строка $$$s$$$ длины $$$n$$$, состоящая из строчных букв латинского алфавита.
Если невозможно разделить строку на подстроки длины большей единицы, начинающиеся и заканчивающиеся на одну и ту же букву, выведите $$$-1$$$.
В противном случае, в первую строку выведите $$$k$$$ — максимальное число подстрок, на которые можно разделить строку $$$s$$$. Во вторую строку выведите $$$k$$$ целых чисел — размеры подстрок, на которые можно разделить строку $$$s$$$, в порядке слева направо. Сумма выведенных $$$k$$$ чисел должна быть равна $$$n$$$.
4 aaaa
2 2 2
15 abcbcaccbbcabca
3 6 5 4
4 abcd
-1
5 abcda
1 5
В первом примере можно разделить строку на две подстроки длины два, каждая из которых будет начинаться и заканчиваться буквой a.
Во втором примере можно разделить строку на три подстроки abcbca, ccbbc и abca.