다다스와 쿼리

길이 $N$의 목표 수열 $A=[A_1,A_2,\cdots,A_N]$이 주어진다.

길이 $N$의 작업 수열 $B=[B_1,B_2,\cdots,B_N]$를 생각하자. 처음에는 모든 가 이다. 다음 시행을 원하는 만큼 할 수 있다.

• 두 정수 $l,r$을 골라 $1\le l\le r\le N$을 만족하게 한다.
• 정수 $y$를 $1$ 또는 중 하나로 고른다.

작업 수열 $B$를 목표 수열 $A$와 같게 만드는 데 필요한 시행 횟수의 최솟값을 $A$의 비용이라고 하자.

단순히 비용을 구하는건 너무 쉽다고 생각한 다다스는 $Q$개의 업데이트 쿼리를 추가하기로 했다. 각 쿼리는 목표 수열 $A$의 원소 하나를 새로운 값으로 바꾼다. 각 쿼리가 적용된 직후 현재 목표 수열 $A$의 비용을 구하여라.

각 쿼리의 비용을 계산할 때 작업 수열 $B$는 항상 모든 원소가 $0$인 상태에서 시작한다. 이전 쿼리에서 수행한 시행은 다음 쿼리로 이어지지 않는다.

입력은 다음과 같은 형식으로 주어진다.

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

각 테스트 케이스마다 $Q$개의 줄을 출력한다.

$j$번째 줄에는 $j$번째 쿼리를 적용한 직후 현재 목표 수열 $A$의 비용을 출력한다.

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