Increasing Addition Codechef Solution

Problem

You have an array $A$ of length $N$. In one operation, you can do the following:

• Select any subarray A_{L \ldots R}AL…R​ $(1\le L\le R\le N)$ and then add $i$ to the $i$-th element of this subarray. Formally, we set A_j := A_j + (j – L + 1)Aj​:=Aj​+(j−L+1) for all $L\le j\le R$.

For example: if $A=[2,1,5,2]$ and we apply operation on A_{2 \ldots 4}A2…4​ then $A$ becomes $[2,1+1,5+2,2+3]=[2,2,7,5]$.

The minimum number of such operations required to sort $A$ in non-decreasing order is termed as the goodness of $A$.

We want to process $Q$ updates on $A$ of the following form:

• $\text{i x}$ : Set A_i := xAi​:=x where ($1\le i\le N$).

Determine the goodness of $A$ after each update.

Input Format

• The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains two integers $N$ and $Q$ — the size of the array $A$ and the number of updates.
• The second line of each test case contains $N$ space-separated integers A_1, A_2, \dots, A_NA1​,A2​,…,AN​ denoting the array $A$.
• The next $Q$ lines each contain two integers $i$ and $x$ denoting the parameters of the update.

Output Format

For each test case, output $Q$ integers, the goodness of the array after each update.

Constraints

Subtasks

Sample 1:

2
3 2
3 2 1
3 10
2 1
4 2
2 2 2 2
4 2
4 1

1
2
0
1

Explanation:

Test Case 1: Initially $A=[3,2,1]$.

• After first update: $A=[3,2,10]$.
  • Now we can apply the operation on A_{1 \ldots 2}A1…2​. Then $A$ becomes $[4,4,10]$. Therefore the goodness of $A$ is $1$.
• After second update: $A=[3,1,10]$.
  • Now we can apply the operation on A_{2 \ldots 2}A2…2​. $A$ becomes $[3,2,10]$. Now again we can apply the operation A_{2 \ldots 2}A2…2​. $A$ becomes $[3,3,10]$. Therefore the goodness of $A$ is $2$.

Test Case 2: Initially $A=[2,2,2,2]$.

• After first update: $A=[2,2,2,2]$.
  • $A$ is already in sorted order. Therefore the goodness of $A$ is $0$.
• After second update: $A=[2,2,2,1]$.
  • Now we can apply the operation on A_{3 \ldots 4}A3…4​. $A$ becomes $[2,2,3,3]$. Therefore the goodness of $A$ is $1$.