SOLVE

LATER

Shift and Replace

/

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.

- Change the value of any element (only one element).
- Perform cyclic shifts to the array to left by
**1**unit. For example, if an array is \(2\ 3\ 1\ 4\) and**1**left shift is performed, then the array becomes \(3\ 1\ 4\ 2\).

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**

- The first line contains \(N\) denoting the number of elements in the array.
- The second line contains \(N\) space-separated integers.
- The next line contains \(Q\) denoting the number of queries.
- The next
**\(Q\)**lines contain queries of type \(X\ B\).

**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\)

Explanation

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.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...