Дана строка 
S длины N, состоящая только из 0 и 1. Для каждого R от 1 до N необходимо найти любой индекс 1≤L<R такой, что S_R является медианой подстроки S[L…R].
Определение: медиана строки S, состоящей только из 0 и 1, определяется следущим образом:
обозначим за C_0 количество 0 в строке S; аналогично C_1 — количество 1.
пусть C_0>C_1 — в таком случае медианой является 0; аналогично при C_0<C_1 медианой является 1.
в случае C_0=C_1 медианой считается значение 0.5 (в рамках данной задачи достаточно знать, что данная медиана не равна ни 0, ни 1).
Пожалуйста, ознакомьтесь с примерами тестов и пояснениями к ним для лучшего понимания условия.
Формат ввода
В первой строке вводится целое число 
N (2≤N≤10^6)  — количество символов в строке S.
Во второй строке вводится строка 
S длины N, состоящая только из символов 0 и 1.

Формат вывода
Выведите 
N индексов L_R, где 1≤L_R<R и S_R равно медиане отрезка 
S[LR…R].
Если для R не существует подобного индекса L_R, то необходимо вывести −1.
Заметьте, что для 
R=1 ответа не существует по определению.

Первый тестовый пример:
Ввод:
5
01001
Вывод:
-1 -1 1 1 -1 
Второй тестовый пример:
Ввод:
5
01011
Вывод:
-1 -1 1 2 2 
Третий тестовый пример:
Ввод:
4
0010
Вывод:
-1 1 -1 1

Примечания
Рассмотрим ответы на первый тестовый пример 
S=01001:
L_1=−1 по определению;
L_2 может быть равно только 1 или −1.
Медиана подстроки S[1…2]=01 равна 0.5 по определению, что не равно 
S_2 =1. Поэтому L_2=−1.
L_3=1, так как S_3=0 и медиана подстроки S[1…3]=010 равна 0(C_0=2, C_1=1).
L_4=1, так как S_4=0 и медиана подстроки S[1…4]=0100 равна 0.
Обратите внимание, что L_4=2 и L_4=3 также являются верными ответам, так как медианы подстрок S[2…4]=100 и S[3…4]=00 также равны 0.
L_5=−1, так как S_5=1 и:
медианы подстрок S[1…5]=01001 и S[3…5]=001 равны 0;
медианы S[2…5]=1001 и S[4…5]=01 равны 0.5.
Рассмотрим ответы на второй тестовый пример S=01011:
L_1=−1 по определению;
L_2=−1, так как S_2=1, а медиана единственной возможной подстроки 
S[1…2]=01 равна 0.5.
L_3=1, так как S_3=0 и медиана подстроки S[1…3]=010 равна 0.
L_4=2, так как S_4=1 и медиана подстроки S[2…4]=101 равна 1.
L_5=2, так как S_5=1 и медиана подстроки S[2…5]=1011 равна 1.
Обратите внимание, что L_5=1, L_5=3 и L_5=4 также являются верными ответами, так как медианы подстрок S[1…5]=01011, S[3…5]=011 и S[4…5]=11 аналогично равны 1.

Рассмотрим ответы на третий тестовый пример 
S=0010:
L_1=−1 по определению;
L_2=1, так как S_2=0 и медиана подстроки S[1…2]=00 равна 0.
L_3=−1, так как S_3=1, а медианы всех возможных подстрок S[1…3]=001 и S[2…3]=01 равны 0 и 0.5 соответственно.
L_4=1, так как S_4=0 и медиана подстроки S[1…4]=0010 равна 0.
Обратите внимание, что L_4=2 тоже является верным ответом, так как медиана подстроки S[2…4]=010 равна 0.