USACO 2006, poj 3250- 불쾌한 날(Bad Hair Day) > 문제은행 : 정보올림피아드&알고리즘




1141 : 불쾌한 날(Bad Hair Day)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
379 회   
시도횟수
1450 회   

문제

농부 시현이의 N(1≤N≤80,000)마리의 소들은 "bad hair day"를 맞이하였다. 

각 소들이 자신들의 촌스런 머리 모양을 부끄러워 하자, 시현이는 소들이 다른 소들의 머리 모양을 얼마나 알 수 있는지를 알고자 했다.


i번째 소들은 키가 hi(1≤hi≤1,000,000,000) 이며, 동쪽(오른쪽)을 바라보고 서있다. 

따라서, i번째 소는 자신의 앞 ( i+1, i+2,...)의 소들의 머리 모양만 볼 수 있으며, 앞에 자신의 키보다 작은 소들만 볼 수 있다.


 


다음 예제를 고려해보자: ()의 숫자는 키를 나타낸다.

1번 소는 2,3,4번소의 머리 모양을 볼 수 있다.

2번 소는 어떤 소의 머리 모양도 볼 수 없다.

3번 소는 4번 소의 머리 모양을 볼 수 있다.

4번 소는 어떤 소의 머리 모양도 볼 수 없다. 

5번 소는 6번 소의 머리 모양을 볼 수 있다.

6번 소는 모든 소들의 머리 모양을 볼 수 없다!


i번 소들이 볼 수 있는 머리 모양의 수를 Ci 이라고 할 때, C1부터 CN 까지의 합을 출력하는 프로그램을 작성하라. 

위의 예제의 답은 3+0+1+0+1+0=5가 된다.


입력형식

입력의 첫 번째 행에는 N 이 입력된다.

그 다음 줄부터 N 개의 숫자가 행을 구분하여 주어지며, 해당 행의 i번째 숫자는 hi를 뜻한다.


출력형식

C1 부터 CN 까지의 합을 한 줄에 출력한다.

입력 예

6
5
2
4
2
6
1

출력 예

5


스택큐

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP