Shift and Replace
Tag(s):

## 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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

March Circuits '20

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Math > Number Theory
• Algorithms > Graphs
• Math > Linear Algebra
• Data Structures > Arrays