Professor Higashikata

Josuke is tired of his peaceful life in Morioh. Following in his nephew Jotaro's footsteps, he decides to study hard and become a professor of computer science. While looking up competitive programming problems online, he comes across the following one:

Let $$$s$$$ be a binary string of length $$$n$$$. An operation on $$$s$$$ is defined as choosing two distinct integers $$$i$$$ and $$$j$$$ ($$$1 \leq i < j \leq n$$$), and swapping the characters $$$s_i, s_j$$$.

Consider the $$$m$$$ strings $$$t_1, t_2, \ldots, t_m$$$, where $$$t_i$$$ is the substring $$$^\dagger$$$ of $$$s$$$ from $$$l_i$$$ to $$$r_i$$$. Define $$$t(s) = t_1+t_2+\ldots+t_m$$$ as the concatenation of the strings $$$t_i$$$ in that order.

There are $$$q$$$ updates to the string. In the $$$i$$$-th update $$$s_{x_i}$$$ gets flipped. That is if $$$s_{x_i}=1$$$, then $$$s_{x_i}$$$ becomes $$$0$$$ and vice versa. After each update, find the minimum number of operations one must perform on $$$s$$$ to make $$$t(s)$$$ lexicographically as large$$$^\ddagger$$$ as possible.

Note that no operation is actually performed. We are only interested in the number of operations.

Help Josuke in his dream by solving the problem for him.

$$$\dagger$$$ A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

$$$\ddagger$$$ A string $$$a$$$ is lexicographically larger than a string $$$b$$$ of the same length if and only if the following holds:

• in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a $$$1$$$, and the string $$$b$$$ has a $$$0$$$.