Informatica Online Judge

  Undirected Bad Hair Day [1237 / 04D5]

Time Limit(Test case) : 1500 (ms)
Number of users who solved : 59   Total Tried : 95


The Champion of this Problem (C++) : gs15040 - ms / 498byte
My Best Submission (C++) : N/A

[JKJeong 2015]

Background

경곽이의 N마리의 소들이 오늘따라 유난히 머리스타일이 맘에 들지 않았다.

경곽이는 소들의 머리스타일을 확인시키기 위해 소들을 일렬로 세워놓았다.

그리고 각 소들이 다른 소들의 머리스타일을 얼마나 많이 확인 할 수 있는지 궁금해졌다.

i번째 소의 키를 hi라고 할 때 소들은 자신의 왼쪽과 오른쪽에 있는 소들 즉, 양쪽 모두를 바라본다.

단, 이번 젖소들은 모두 왼쪽의 시야가 더 발달했다.

따라서, 왼쪽의 소들은 자신과 키가 같거나 작은 소들을 모두 바라볼 수 있다. 하지만 오른쪽은 자신 보다 작은 소들만 바라볼 수 있다.


당연히 자신보다 키가 큰 소 넘어 존재하는 소들은 바라볼 수 없다.

따라서 원래 문제와는 다르다.

각 소들이 머리스타일을 확인할 수 있는 수의 총 합을 구하는 프로그램을 작성하시오.

다음은 한 예를 나타낸다. 소의 수가 6이고 키가 { 10, 3, 7, 4, 12, 2 }이라고 할 경우




1번소는 { 2, 3, 4 }번소의 머리스타일을 확인할 수 있고,

2번소는 다른 소들의 머리스타일을 확인할 수 없다.

3번소는 { 3, 4 }번소의 머리스타일을 확인할 수 있으며,

4번소도 2번 소와 마찬가지로 다른 소의 머리스타일을 확인할 수 없다.

5번소는 { 1, 2, 3, 4, 6 }번소의 머리스타일을 확인할 수 있고,

6번소 키가 작아 다른 소의 머리스타일을 확인할 수 없다.

즉, 자신 보다 키가 작은 소가 있더라도, 자신과 작은 소 사이에 자신보다 큰 소가 있을 경우 그 소를 확인하지 못한다.

따라서, 머리스타일을 확인할 수 있는 총 수는 3 + 0 + 2 + 0 + 5 + 0 = 10이다.

Input

입력은 키보드로 부터 들어온다.
첫 번째 줄에는 소의 수를 나타내는 N이 주어지며
두 번째 줄부터 N+1번째 줄까지 각 소들의 키가 주어진다.

[입력값의 정의역]
1 <= N <= 100,000
1 <= hi <= 1,000,000,000

Output

각 소들이 확인할 수의 총 합을 출력한다

IO Example

입력1
6
10 3 7 4 12 2

출력1
10

입력2
5
1 1 1 1 1

출력2
10

- 입력예 2의 경우 오른쪽으로는 모두 0을 볼 수 있지만 왼쪽으로는 0 1 2 3 4마리를 볼 수 있으므로 10마리이다. (왼쪽으로는 키가 같아도 바라볼 수 있다.)

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