Problem
새로운 게임(볼링과 당구의 일부 하이브리드)을 할 때 1부터 N까지 번호가 매겨진 N개의 공이 사용됩니다. 게임 시작 시 이 공은 숫자 순서대로 일렬로 배치되어야 합니다. 게임 도중 순서가 바뀔 수 있습니다.
다음 게임이 시작되기 전에 공을 정리하기 위해 다음 장치를 사용합니다. 이 장치는 볼 위로 이동하여 "빨아"낼 수 있는 헤드로 구성됩니다. 그리고 "뱉어" 풍선. 이 장치에 대한 더 나은 아이디어를 얻으려면 공을 빨아들이고 올바른 위치로 이동한 다음 반대 방향으로 불고 공을 "뱉어내는" 진공 청소기를 상상해 보십시오.
풍선을 빨면 오른쪽에 있던 풍선이 모두 왼쪽으로 이동합니다. "뱉다" 공은 두 개의 공 사이에 있을 수 있습니다(첫 번째 공 앞이나 마지막 공 뒤에도 있음). 그런 다음 이 공 사이에 침을 뱉는 공을 삽입하고 삽입된 공의 오른쪽에 있는 모든 공은 오른쪽으로 이동합니다. .
한 번에 하나 이상의 공을 장치로 빨 수 있으며 공을 뱉을 때 마지막으로 빨린 공을 먼저 뱉은 다음 끝에서 두 번째 공을 뱉는 식입니다. (즉, 장치는 스택 원리로 작동합니다). 공은 한 번에 하나씩 뱉어집니다. 하나의 공만 뱉어내고 나머지는 장치 내부에 남겨둘 수 있습니다(이 경우 공을 같은 위치 또는 다른 위치에 계속 "뱉어내거나" 새 공을 빨아들일 수 있음).
설명된 작업 중 가장 에너지 집약적인 작업은 공을 빨아들이는 작업이므로 이러한 작업의 수를 최소화하고자 합니다.
공의 초기 배열이 주어지면 공을 숫자 순서로 배열하는 데 필요한 최소 흡입 횟수를 결정하는 프로그램을 작성하십시오.
입력
입력 파일에서 숫자 N이 먼저 제공됩니다. — 볼 수(1≤N≤1000). 그런 다음 현재 위치에서 왼쪽에서 오른쪽으로 공의 번호를 제공하는 N개의 번호가 있습니다(각 번호는 1에서 N까지이며 각 번호는 순서에서 정확히 한 번 나타납니다).
출력
단일 숫자 출력 — 공을 번호 순서대로 정렬하는 데 필요한 최소 공 흡입 작업 수입니다.
샘플 테스트에 대한 의견
1.예를 들어 2번 풍선을 빨고 1번과 3번 풍선 사이에 뱉어낼 수 있습니다.
2.>이렇게 하면 됩니다. 먼저
풍선 번호 1을 빨아들인 다음 – 공 번호 2. 그런 다음 시작 부분으로 이동하여 4번째 공 앞에서 공을 뱉습니다(이 공은 공 번호 2가 됩니다). 다음으로 3번 풍선을 빨고 2번과 4번 사이에 뱉어낸 다음 처음으로 이동하여 1번 풍선을 뱉어냅니다.
<몸>
| 입력 |
출력 |
|
<사업부>3
2 1 3
|
1 |
|
<사업부>4
4 3 2 1
|
3 |
팀 올림피아드, 모스크바 팀 올림피아드, 9-11학년, 2007, 리그 A, 문제 F