시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (하단 참고) 512 MB 1 1 1 100.000%

문제

총 N개의 블록이 일렬로 놓여져 있다. 가장 왼쪽에 있는 블록의 번호는 1번이고, 그 오른쪽에 있는 블록은 2번이다. 이런식으로 가장 오른쪽에 있는 블록의 번호는 N번이다. i번 블록의 높이는 Hi이다.

블록 게임을 하려면 블록의 앞에 작은 기계를 하나 놓아야 한다. 가장 처음에 이 기계는 1번 블록의 앞에 있다. 블록 게임의 목표는 기계를 이용해 블록을 모두 제거하는 것이다. 이때, 제거한 순서대로 블록의 높이를 나열한 수열은 비내림차순(non-descreasing order)을 만족해야 한다.

기계가 수행할 수 있는 명령은 다음과 같은 세 가지이다.

  • 오른쪽 블록으로 이동한다. i번 블록 앞에 있었으면, i+1번 블록 앞으로 이동한다. 만약, 오른쪽에 블록이 없으면 이 명령을 내릴 수 없다.
  • 왼쪽 블록으로 이동한다. i번 블록 앞에 있었으면, i-1번 블록 앞으로 이동한다. 만약, 왼쪽에 블록이 없으면 이 명령을 내릴 수 없다.
  • 기계의 앞에 있는 블록을 제거하고, 왼쪽 또는 오른쪽 블록으로 이동한다. 제거한 후에 이동하는 방향도 정해서 이 명령을 내려야 한다. 블록을 모두 제거해 양쪽에 블록이 없는 경우에는 이동하지 않아도 된다.

제거하는 명령을 내렸을 때, 블록의 번호가 변하게 된다. 예를 들어, 블록의 높이가 (2, 3, 4, 5, 6)이고, 기계가 현재 높이가 4인 블록 앞에 있는 경우가 있다. 높이가 4인 블록은 왼쪽에서부터 3번째에 있기 때문에, 3번이다. 이 블록을 제거하고 왼쪽으로 이동하면, 블록의 높이는 (2, 3, 5, 6)이 되고 블록은 높이가 3인 블록(2번 블록) 앞에 있게 된다. 만약, 오른쪽으로 이동하면, 블록의 높이는 (2, 3, 5, 6)이 되고 블록은 높이가 5인 블록(3번 블록) 앞에 있게 된다.

게임의 목표를 달성하기 위해 필요한 명령의 최소 횟수를 구하는 프로그램을 작성하시오. 

길이가 K인 수열 A1, A2, ..., AK가 A1 ≤ A2 ≤ ... ≤ AK를 만족하면, 비내림차순(non-decreasing order)이라고 한다. 

입력

첫째 줄에 블록의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 블록의 높이 Hi가 순서대로 주어진다. (1 ≤ Hi ≤ 100,000)

출력

첫째 줄에 게임의 목표를 달성하기 위해 필요한 명령의 최소 횟수를 출력한다.

서브태스크 1 (7점)

  • 1 ≤ N ≤ 1,000
  • 1 ≤ Hi ≤ 1,000
  • Hi는 중복되지 않음

서브태스크 2 (14점)

  • 1 ≤ N ≤ 1,000
  • 1 ≤ Hi ≤ 100,000
  • Hi는 중복되지 않음

서브태스크 3 (20점)

  • 1 ≤ N ≤ 100,000
  • 1 ≤ Hi ≤ 100,000

예제 입력 1

3
1 2 3

예제 출력 1

3

예제 입력 2

4
4 2 1 3

예제 출력 2

6

예제 입력 3

5
5 5 1 5 5

예제 출력 3

7

예제 입력 4

10
10 8 6 4 2 1 3 5 7 9

예제 출력 4

15

예제 입력 5

10
1 3 5 7 9 10 8 6 4 2

예제 출력 5

46

힌트

예제 1의 경우에는 기계에 명령을 다음과 같이 내리면 된다. 밑 줄이 쳐있는 블록의 앞에 기계가 있다.

  • 처음 상태: 1 2 3
  • 블록을 제거하고, 오른쪽으로 이동: 2 3
  • 블록을 제거하고, 오른쪽으로 이동: 3
  • 블록을 제거

예제 2의 경우에는 다음과 같이 명령을 내려야 한다.

  • 처음 상태: 4 2 1 3
  • 오른쪽으로 이동: 4 2 1 3
  • 오른쪽으로 이동: 4 2 1 3
  • 블록을 제거하고 왼쪽으로 이동: 4 2 3
  • 블록을 제거하고 오른쪽으로 이동: 4 3
  • 블록을 제거하고 왼쪽으로 이동: 4
  • 블록을 제거

 

출처

  • 문제의 오타를 찾은 사람: doju

시간 제한 안내

아래 적혀있지 않은 시간 제한은 언어 도움말에 적혀있는 기준을 따른다.

  • Python 3: 12초
  • PyPy3: 12초
  • Python 2: 12초
  • PyPy2: 12초

채점

  • 예제는 채점하지 않는다.