Dadas and Queries

A target sequence $A=[A_1,A_2,\cdots,A_N]$ of length $N$ is given.

Consider a working sequence $B=[B_1,B_2,\cdots,B_N]$ of length . Initially, every is . You may perform the following operation any number of times.

• Choose two integers $l,r$ satisfying $1\le l\le r\le N$.
• Choose $y$ to be either $1$ or .

The cost of $A$ is the minimum number of operations required to make the working sequence $B$ equal to the target sequence $A$.

Then, $Q$ update queries are given. Each query replaces one element of the target sequence $A$ with a new value. After each query, find the cost of the current target sequence $A$.

When computing the cost after each query, the working sequence $B$ always starts with every element equal to $0$. Operations performed for an earlier query do not carry over to a later query.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, print $Q$ lines.

On the $j$-th line, print the cost of the current target sequence $A$ immediately after applying the $j$-th query.

• $1\le T\le 200\,000$.
• $1\le N,Q\le 200\,000$.
• .