새내기 주간

새내기 주간에 학생들은 서로를 알아가고 다른 팀과 겨루기 위해 다양한 게임을 한다. 그중 한 게임에서는 한 팀의 새내기 전원이 한 줄로 서고, 키, 생년월일, 학번 같은 어떤 기준에 따라 스스로 줄을 다시 선다. 줄을 다시 서는 과정은 오직 이웃한 두 학생의 자리를 맞바꾸는 동작만을 반복하여 이루어져야 한다. 가장 빨리 끝낸 팀이 이긴다. 따라서 이기려면 필요한 교환 횟수를 최소로 만들어야 한다.

첫째 줄에 팀의 학생 수를 나타내는 양의 정수 $n$ 이 주어진다 ($1 \le n \le 1{,}000{,}000$). 다음 $n$ 개의 줄에는 각 학생의 학번이 한 줄에 하나씩, 정수로 주어진다. 같은 학번은 두 번 이상 나타나지 않는다.

학번이 증가하는 순서가 되도록 학생들을 정렬하는 데 필요한 최소 교환 횟수를 한 줄에 출력한다.