파일 업로드

원반 던지기

profile
실행 시간 제한메모리 제한
1 초1024 MB
📃 해결할 문제

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

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

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

💻 입력

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

🖨️ 출력

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


💻 예제 입력 1
7
4 3 1 2 5 6 7
🖨️ 예제 출력 1
24

💡 힌트

선수 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