원반 던지기

실행 시간 제한	메모리 제한
1 초	1024 MB

📃 해결할 문제

스포츠 팀의 $N$ 명의 선수들 ( $N \leq 3 \times 10^5)$ 은 키가 각각 $1, 2, \ldots, N$ 입니다. 어느 날, 선수들이 일렬로 서서 원반 던지기 게임을 하고 있습니다. 선수들의 순서를 $h_1 \ldots h_N$ 로 표시하겠습니다(즉, $h$ 값들은 $1 \ldots N$ 의 순열입니다).

선수들 중 라인에서 $i$ 위치와 $j$ 위치에 서 있는 두 명이 원반을 성공적으로 주고받으려면 그들 사이에 있는 모든 선수의 키가 $\min(h_i, h_j)$ 보다 낮아야 합니다.

선수들이 원반을 성공적으로 주고받을 수 있는 모든 위치 쌍 $i\ltj$ 사이의 거리 합을 계산하세요. 위치 $i$ 와 $j$ 사이의 거리는 $j-i+1$ 입니다.

💻 입력

입력의 첫 번째 줄에는 정수 $N$ 이 포함되어 있습니다. 입력의 다음 줄에는 공백으로 구분된 $h_1 \ldots h_N$ 이 포함되어 있습니다.

🖨️ 출력

원반을 주고받을 수 있는 모든 위치의 쌍 사이의 거리 합을 출력하세요. 이 문제에서 다루는 정수의 크기가 크기 때문에 64비트 정수 데이터 타입 (예: C/C++의 "long long")이 필요할 수 있습니다.

💻 예제 입력 1

7
4 3 1 2 5 6 7

🖨️ 예제 출력 1

💡 힌트

선수 7명이 일렬로 서 있고, 그들의 키 순서는 다음과 같습니다:

4,3,1,2,5,6,7

이제 원반을 성공적으로 주고받을 수 있는 선수 쌍을 찾아보겠습니다.
예를들면, 선수 1 (키 4)과 선수 2 (키 3)은 서로 주고받을 수 있습니다. 그들 사이에 있는 선수의 키는 모두 두 선수 중 더 작은 선수의 키 3보다 작습니다. 따라서 거리는 2입니다. 이와 비슷하게 다음과 같은 선수 쌍이 있을 수 있습니다.

(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7)

출처: USACO 2022 January Contest, Silver Problem 2. Cow Frisbee