All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Shift and Replace
/

Algorithms, Dynamic Programming, Introduction to Dynamic Programming 1, Segment tree

Problem
Editorial
Analytics

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.

  1. Change the value of any element (only one element).
  2. 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\)

SAMPLE INPUT
4
2 1 2 3
3
1 1
1 4
4 40
SAMPLE OUTPUT
2
1
2
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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?