Informatica Online Judge

  다산왕의 공연관람 [1026 / 0402]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 38   Total Tried : 53


The Champion of this Problem (C++) : gs15120 - 3ms / 1283byte
My Best Submission (C++) : N/A

[koistudy.net (31st 임성배)]

Background

다산왕 P씨는 우리나라 출산율 상승에 크게 공헌한 사람 중 한명이다. 그녀에게는 n명의 일란성쌍둥이가 있다.

어느 날 그녀는 n명의 아기를 모두 데리고 산책을 하던 도중 재밌는 공연을 발견하여 아기들에게 보여주려고 한다.

그런데 아기들은 너무 무질서하여 그녀는 아기들을 일렬로 세워 공연을 보여주고 싶었다.

여기서 또 문제가 발생하는데, 뒤에 앉은 아기들은 앞사람 때문에 공연관람이 힘들어서 울기 마련이었다.

그녀는 좋은 묘책이 떠올랐다. 그녀의 남편은 방석공장을 운영하고 있어서 방석이 많은데, 뒤에 아기들이 방석을 깔고 앉으면 앞사람 때문에 공연이 보이지 않을 문제가 해결될 것이기 때문이다.



그녀는 아기들에게 방석을 나누어주었는데, 또 문제가 생겼다. 정말 아기들은 문제 투성이이다.

아기들이 방석을 임의의 개수대로 가지고 가자, 자기보다 높은 방석에 앉은 아기가 앞에 존재하면 울게 되었다.

그래서 그녀는 아기들이 울지 않도록 아기들에게 방석을 나누어주었다.
아기들이 우는 상황은 다음과 같다.

1. 두 칸 이상 떨어져 있는 사람들 중에 자신의 방석 높이보다 큰 사람이 있으면 운다.
2. 한칸 떨어져 있는 바로 앞 사람보다 자신의 방석 높이가 같거나 작으면 운다.



이 때, 아가들의 수와 초기의 아기들이 가져간 방석의 개수가 주어질 때, 다산왕 P씨가 아기들이 울지 않을 때까지 주어야 할 방석의 총 개수의 최솟값을 출력하는 프로그램을 작성하시오.

Input

첫 번째 줄에 아기의 수를 나타내는 N이 입력된다.
다음 줄에 N명의 아기가 가져간 방석의 개수를 앞에서부터 차례로 공백으로 구분되어 입력된다.

[입력값의 정의역]
1<= N <= 1000000

Output

다산왕이 아기들에게 주어야 할 방석의 총 개수의 최솟값을 구하시오

IO Example

입력
7
1 3 1 2 2 5 3

출력
17

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]