Farmer John은 소들이 아침을 먹으러 목초지로 나가기 전에, 편리하게 \(1\)번부터 \(N\)번까지 번호가 붙은 \(N\)마리의 소를 정렬하려고 한다. \((1 \le N \le 100)\)

현재 소들은 \(p_1,p_2,p_3,\dots,p_N\)의 순서로 한 줄에 서 있고, Farmer John은 \(p_1\)번 소의 앞에 서 있다. Farmer John은 \(1\)번 소가 자신의 바로 옆에 오도록 소들을 \(1,2,3,\dots,N\)의 순서로 다시 배열하려고 한다.

오늘 소들은 조금 졸려서, 어느 순간이든 Farmer John의 지시에 주의를 기울이는 소는 Farmer John을 바로 마주 보고 있는 소뿐이다. 한 번의 시간 단계에서 Farmer John은 이 소에게 줄을 따라 뒤쪽으로 \(k\)칸 이동하라고 지시할 수 있다. 이때 \(1 \le k \le N-1\)이다. 이 소가 지나치는 \(k\)마리의 소들은 앞으로 천천히 이동하여, 그 뒤에 이 소가 들어갈 자리를 만든다.

예를 들어 \(N=4\)이고 소들이 처음에 다음 순서로 서 있다고 하자.

FJ: 4 3 2 1

Farmer John의 지시에 주의를 기울이는 소는 \(4\)번 소뿐이다. Farmer John이 이 소에게 줄을 따라 뒤쪽으로 \(2\)칸 이동하라고 지시하면 소들의 순서는 다음과 같이 바뀐다.

FJ: 3 2 4 1

이제 Farmer John의 지시에 주의를 기울이는 소는 \(3\)번 소뿐이다. 따라서 두 번째 시간 단계에서는 \(3\)번 소에게 지시할 수 있으며, 소들이 정렬될 때까지 같은 과정을 계속할 수 있다.

Farmer John은 정렬을 빨리 끝내고 농가로 돌아가 자신의 아침 식사를 하고 싶어 한다. 소들을 정렬하는 데 필요한 최소 시간 단계의 수를 구하여라.

입력

첫째 줄에 \(N\)이 주어진다.

둘째 줄에 소들의 처음 순서를 나타내는 \(N\)개의 정수 \(p_1,p_2,p_3,\dots,p_N\)이 공백으로 구분되어 주어진다.

출력

Farmer John이 최적으로 행동할 때, \(N\)마리의 소가 정렬될 때까지 필요한 시간 단계의 수를 출력한다.

예제 입력 1

4
1 2 4 3

예제 출력 1

3

출처

USACO 2019 January Contest, Bronze, Problem 2. Sleepy Cow Sorting