You are given an array \(A\) of \(N\) integers. The following two operations can be performed on the provided array and each operation costs 1 unit.
You are given \(Q\) queries of type \(X\ B\). For each query, you must replace the value of the element at index \(X\) with \(B\). Find the minimum cost required to convert array \(A\) to the identity array.
An identity array of size \(N\) is \(1,\ 2,\ 3,\ ...,\ N-1,\ N\).
Note: For each query, you cannot perform actual operations on array \(A\) apart from setting \(A[X]\) to \(B\).
Input format
Output format
Print \(Q\) integers in a separate line representing the answer to \(Q\) queries.
Constraints
\(1 \le N,\ Q \le 1e5\\
1 \le X \le N\\
1 \le A[i],\ B \le 10^9\)
Initial array after Query 1, [1,1,2,3]. Minimum cost is 2. Cyclic Shift once and replace value of last index to be 4.
Array after Query 2, [4,1,2,3]. Minimum cost is 1. Cyclic Shift once.
Array after Query 3, [4,1,2,40]. Minimum cos is 2. Cyclic Shift once, replace 3rd element with 3.