Джосуке устал от спокойной жизни в Мориохе. Пойдя по стопам своего племянника Дзётаро, он решает упорно учиться и стать профессором информатики. Просматривая в Интернете задачи по программированию, он наткнулся на следующую.
Пусть \(s\) — бинарная строка длины \(n\). Операция над \(s\) определяется как выбор двух различных целых чисел \(i\) и \(j\) (\(1 \leq i < j \leq n\)), и обмен местами символов \(s_i, s_j\).
Рассмотрим \(m\) строк \(t_1, t_2, \ldots, t_m\), где \(t_i\) — подстрока\(^\dagger\) из \(s\) от \(l_i\) до \(r_i\). Определим \(t(s) = t_1+t_2+\ldots+t_m\) как конкатенацию строк \(t_i\) в таком порядке.
Существует \(q\) обновлений строки. В \(i\)-м обновлении \(s_{x_i}\) инвертируется. То есть, если \(s_{x_i}=1\), то \(s_{x_i}\) становится \(0\) и наоборот. После каждого обновления найдите минимальное количество операций, которые нужно выполнить над \(s\), чтобы сделать \(t(s)\) лексикографически как можно большим\(^\ddagger\).
Обратите внимание, что на самом деле ни одна операция не применяется. Нужно найти только количество операций.
Помогите Йосуке в его мечте, решив за него эту задачу.
—————————————————————— \(\dagger\) Строка \(a\) является подстрокой строки \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, нуля или всех) символов из начала и нескольких (возможно, нуля или всех) символов из конца.
\(\ddagger\) Строка \(a\) лексикографически больше строки \(b\) такой же длины тогда и только тогда, когда выполняется следующее условие:
- в первой позиции, где \(a\) и \(b\) отличаются, в строка \(a\) стоит \(1\), а в строке \(b\) стоит \(0\).
Выходные данные
Выведите \(q\) целых чисел. В строке \(i\) выведите минимальное количество операций, которое необходимо выполнить над \(s\), чтобы получить лексикографически наибольшую возможную строку \(t(s)\) после \(i\)-го обновления.
Примечание
В первом примере:
Изначально \(t(s) = s(1,2) + s(1,2) = 0101\).
После \(1\)-го запроса, \(s\) становится \(11\) и, соответственно, \(t\) становится \(1111\). Никаких операций выполнять не нужно, так как \(t(s)\) уже является лексикографически наибольшей строкой из возможных.
После \(2\)-го запроса \(s\) становится \(01\) и, следовательно, \(t\) становится \(0101\). Необходимо выполнить операцию \(1\), поменяв местами \(s_1\) и \(s_2\). Следовательно, \(t(s)\) становится \(1010\), что является лексикографически наибольшей строкой, которую можно получить.