명령어 히스토리

명령줄 인터페이스(CLI)는 가장 오래된 사람과 컴퓨터 사이의 인터페이스 가운데 하나다. 명령 해석기로 소프트웨어를 조작하며, 보통 텍스트 터미널이나 창에서 쓴다. 명령 해석기의 장점은 키보드만으로 시스템을 다룬다는 점이다. 정교한 그래픽 인터페이스가 익숙해진 오늘날에도 많은 응용 프로그램과 운영체제가 어떤 형태로든 명령줄 인터페이스를 함께 제공하고, 여전히 대부분의 작업을 명령줄로 처리하는 사용자가 많다.

명령 해석기의 유용한 기능 중 하나는 명령어 히스토리다. 명령어를 입력해 실행하면 그 명령어가 터미널의 히스토리에 쌓인다. ↑ 키를 누르면 히스토리에 있는 명령어가 터미널에 다시 표시되고, 표시된 상태에서 Enter 키를 누르면 그 명령어가 다시 실행된다. 실행한 명령어는 모두 히스토리에 남는다. ↑ 키를 두 번 누르면 마지막에서 두 번째로 실행한 명령어가 표시되고, 세 번 누르면 세 번째로 이전에 실행한 명령어가 표시되며, 이런 식으로 계속된다.

예를 들어 처음 히스토리가 (A, B, C, D)라면 명령어 C를 다시 실행하려면 ↑ 키를 두 번 누르면 된다. 그러면 히스토리는 (A, B, C, D, C)로 바뀐다. 이 상태에서 명령어 A를 다시 실행하려면 ↑ 키를 다섯 번 눌러야 하고, 히스토리는 (A, B, C, D, C, A)가 된다. 이 상태에서 명령어 A를 한 번 더 실행하려면 ↑ 키를 한 번만 누르면 되고, 히스토리는 (A, B, C, D, C, A, A)가 된다.

레안드로는 시스템 관리자여서 자신이 맡은 원격 서버를 관리할 때 명령 해석기를 자주 쓴다. 평소에는 전에 입력해 둔 명령어를 다시 실행하기만 한다. 어느 날 서버에서 작업하다가 정해진 순서대로 명령어를 실행하려면 ↑ 키를 몇 번 눌러야 하는지 의문이 들었다. 실행할 명령어가 히스토리의 어느 위치에 있는지는 알지만 이 문제를 푸는 방법은 모른다. 그래서 답을 구하는 프로그램을 만들어 달라고 부탁했다.

레안드로는 원하는 명령어를 표시하는 데 필요한 최소 횟수만큼만 ↑ 키를 누른다. 처음 히스토리에서 위치가 서로 다른 명령어는 서로 다른 명령어이고, 같은 명령어가 히스토리에 여러 번 들어 있으면 그중 가장 가까운 것을 쓴다.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 레안드로가 실행할 명령어의 개수 $N$이 주어진다 ($1 \le N \le 1000$). 둘째 줄에는 $N$개의 정수 $P_1, P_2, \dots, P_N$이 명령어를 실행하는 순서대로 주어지는데, 이는 처음 히스토리에서 각 명령어가 있는 위치다 ($1 \le P_i \le 10^6$). 즉 처음 히스토리의 $P_1$번 위치에 있는 명령어를 가장 먼저 실행하고, 다음으로 $P_2$번 위치에 있는 명령어를 실행하며, 마지막으로 $P_N$번 위치에 있는 명령어를 실행한다. $P_i = P_j$일 수 있다.

위치는 ↑ 키를 눌러야 하는 횟수로 나타낸다. 위치가 5인 명령어는 터미널에 나타나기까지 ↑ 키를 다섯 번 눌러야 한다. 명령어를 하나씩 실행할수록 히스토리에서 어떤 명령어의 위치는 달라질 수 있다.

입력의 마지막 줄에는 $N = 0$이 주어진다. 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 한 줄에 레안드로가 모든 명령어를 실행하는 데 ↑ 키를 누르는 횟수를 출력한다.