Dominating Duos

면접 대비

시간 제한4초메모리 제한512 MB

요약

순열에서 두 끝값이 그 사이의 모든 값보다 큰 쌍 (i, j)의 개수를 n이 10^6까지일 때 센다.

난이도: 보통10점 중 6점
유형: 스택, 배열, 조합론
정답자: 아직 제출이 없습니다

문제

사람들이 한 줄로 서 있다. 각 사람의 키는 서로 다르다. 줄에서 어떤 두 사람 사이에 있는 모든 사람보다 두 사람이 더 큰 경우, 그러한 두 사람의 순서 없는 쌍의 개수를 세려고 한다.

더 형식적으로, 줄에 서 있는 순서대로 사람들의 키를 나열한 수열을 $d$ 라고 하자. $i < j$ 이고 $i < k < j$ 인 모든 $k$ 에 대해 $d_i > d_k$ 이며 $d_j > d_k$ 인 인덱스 쌍 $i, j$ 의 개수를 구하려고 한다. $j = i + 1$ 인 경우(즉, $i$ 와 $j$ 사이에 $k$ 가 없는 경우)에는 이 조건이 자명하게 성립한다.

입력

첫째 줄에 사람 수를 나타내는 정수 $n$ 이 주어진다( $2 \le n \le 10^6$ ).

다음 $n$ 개 줄에 각각 하나의 정수 $d_i$ 가 주어진다( $1 \le d_i \le n$ ). 이 값들은 줄에 서 있는 순서대로 사람들의 키이며, 수열은 $1$ 부터 $n$ 까지의 정수를 한 번씩 포함하는 순열임이 보장된다.

출력

두 사람 사이에 있는 모든 사람보다 두 사람이 더 큰 경우의 쌍의 개수를 정수 하나로 출력한다.

예제2

예제 1
입력
```
3
2
1
3
```
예상 출력
```
3
```
예제 2
입력
```
6
1
3
2
6
4
5
```
예상 출력
```
7
```