[Solution] PermutationForces solution codeforces

PermutationForces solution codeforces – You have a permutation 𝑝p of integers from 11 to 𝑛n.

[Solution] PermutationForces solution codeforces

You have a strength of 𝑠s and will perform the following operation some times:

  • Choose an index 𝑖i such that 1𝑖|𝑝|1≤i≤|p| and |𝑖𝑝𝑖|𝑠|i−pi|≤s.
  • For all 𝑗j such that 1𝑗|𝑝|1≤j≤|p| and 𝑝𝑖<𝑝𝑗pi<pj, update 𝑝𝑗pj to 𝑝𝑗1pj−1.
  • Delete the 𝑖i-th element from 𝑝p. Formally, update 𝑝p to [𝑝1,,𝑝𝑖1,𝑝𝑖+1,,𝑝𝑛][p1,…,pi−1,pi+1,…,pn].

It can be shown that no matter what 𝑖i you have chosen, 𝑝p will be a permutation of integers from 11 to |𝑝||p| after all operations.

You want to be able to transform 𝑝p into the empty permutation. Find the minimum strength 𝑠s that will allow you to do so.

Input

The first line of input contains a single integer 𝑛n (1𝑛51051≤n≤5⋅105)  — the length of the permutation 𝑝p.

The second line of input conatains 𝑛n integers 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn (1𝑝𝑖𝑛1≤pi≤n)  — the elements of the permutation 𝑝p.

It is guaranteed that all elements in 𝑝p are distinct.

[Solution] PermutationForces solution codeforces

Print the minimum strength 𝑠s required.

Examples
input

Copy
3
3 2 1
output

Copy
1

[Solution] PermutationForces solution codeforces

input

Copy
1
1
output

Copy
0
input

Copy
10
1 8 4 3 7 10 6 5 9 2
output

Copy
1

PermutationForces solution codeforces

In the first test case, the minimum 𝑠s required is 11.

Here is how we can transform 𝑝p into the empty permutation with 𝑠=1s=1:

  • In the first move, you can only choose 𝑖=2i=2 as choosing any other value of 𝑖i will result in |𝑖𝑝𝑖|𝑠|i−pi|≤s being false. With 𝑖=2i=2𝑝p will be changed to [2,1][2,1].
  • In the second move, you choose 𝑖=1i=1, then 𝑝p will be changed to [1][1].
  • In the third move, you choose 𝑖=1i=1, then 𝑝p will be changed to [ ][ ].

It can be shown that with 𝑠=0s=0, it is impossible to transform 𝑝p into the empty permutation.

For Solution

Click here

Leave a Comment