1 이상 N 이하의 서로 다른 자연수로 구성된 임의의 수열 a_1..N이 있습니다. GENIUS ainta는 이 수열을 아래 코드를 통해 오름차순으로 정렬하고자 합니다.

이 때, 위 코드를 실행한 뒤 cnt의 값을 구하는 프로그램을 작성하세요.

입력

첫 번째 줄에 수열의 길이 N(1≤N≤500,000)이 주어집니다.
다음 N개의 줄에 a₁,a₂,...,a_N이 각 줄에 하나씩 차례대로 주어집니다.

출력

첫째 줄에 위의 코드를 실행한 뒤 cnt의 값을 출력합니다.

입출력 예

입력

5
2
1
4
5
3

출력

3

출처:GENIUSainta.com