의욕에 찬 Farmer John은 언제나 잘 되지 않는 일을 시도하려 한다. 바로 소 무리 전체의 사진을 찍는 것이다.

사진을 멋지게 만들기 위해 소들을 키가 작은 순서로 한 줄에 세우려 한다. 하지만 줄을 세우자마자 언제나 말썽을 부리는 Bessie가 줄을 나와 다른 위치에 다시 들어간다!

Farmer John은 소 쌍을 서로 바꾸어 전체 무리를 다시 올바른 순서로 정렬하려 한다. 필요한 최소 교환 횟수를 구하도록 도와라.

입력

입력 첫 줄에는 $N$ ($2 \leq N \leq 100$)이 주어진다. 다음 $N$줄은 Bessie가 움직인 뒤 줄에 선 소들의 키를 나타낸다. 각 키는 $1 \ldots 1,000,000$ 범위의 정수이다. 소들의 키가 같을 수 있다.

출력

올바른 순서로 만드는 데 필요한 소 쌍의 최소 교환 횟수를 출력하라. 교환하는 소들은 줄에서 인접하지 않아도 된다.

예제

입력 1

6
2
4
7
7
9
3

출력 1

3

참고

이 예시에서 Bessie는 분명히 키가 3인 소이다. FJ는 아래의 세 교환으로 정렬할 수 있다.

2 4 7 7 9 3 - 원래 줄
2 4 7 7 3 9 - 마지막 두 소를 교환
2 4 3 7 7 9 - 첫 번째 7과 3을 교환
2 3 4 7 7 9 - 4와 3을 교환

문제 출제자: Brian Dean