One-Way Parking - Repovive Starter Round 7 | Repovive

21D. One-Way Parking

2000 pts2s256 MB

There are $n$ parking spaces arranged in a circle and numbered from $1$ to $n$ in clockwise order. There are also $n$ cars, numbered from $1$ to $n$ .

Car $i$ enters the parking area at space $a_i$ . It may park there or continue moving clockwise until it reaches another space. Cars cannot move counterclockwise.

Before any car enters, you must assign a distinct parking space to every car. If a car parks at its entry space, its cost is $0$ . Each move from one space to the next space clockwise increases its cost by $1$ .

Find the minimum possible value of the maximum cost among all cars.

Constraints

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le n$

Input

The input consists of:

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

Output

The output consists of:

D

where $D$ is the minimum possible value of the maximum cost among all cars.

Samples

Input

4
1 2 3 4

Explanation

Assign every car to its entry space. Every car then has cost $0$ .

Output

Input

5
1 1 1 1 1

Explanation

The five cars can be assigned to spaces $1,2,3,4,5$ , giving costs $0,1,2,3,4$ . Since all cars enter at the same space and must receive distinct spaces, no smaller maximum cost is possible.

Output

Input

7
2 2 3 3 5 5 6

Explanation

Assign the cars, in input order, to spaces $2,3,4,5,6,7,1$ . Their costs are $0,1,1,2,1,2,2$ .

A maximum cost of $1$ is impossible: the four cars entering at spaces $2$ and $3$ could then only use spaces $2,3,4$ .

Output

There are $n$ parking spaces arranged in a circle and numbered from $1$ to $n$ in clockwise order. There are also $n$ cars, numbered from $1$ to $n$ .

Car $i$ enters the parking area at space $a_i$ . It may park there or continue moving clockwise until it reaches another space. Cars cannot move counterclockwise.

Find the minimum possible value of the maximum cost among all cars.

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le n$

The input consists of:

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

The output consists of:

D

where $D$ is the minimum possible value of the maximum cost among all cars.

Assign every car to its entry space. Every car then has cost $0$ .

The five cars can be assigned to spaces $1,2,3,4,5$ , giving costs $0,1,2,3,4$ . Since all cars enter at the same space and must receive distinct spaces, no smaller maximum cost is possible.

Assign the cars, in input order, to spaces $2,3,4,5,6,7,1$ . Their costs are $0,1,1,2,1,2,2$ .

A maximum cost of $1$ is impossible: the four cars entering at spaces $2$ and $3$ could then only use spaces $2,3,4$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

21D. One-Way Parking

Constraints

Input

Output

Samples

21D. One-Way Parking

Constraints

Input

Output

Samples