31858번 - 간단한 순열 문제

문제

길이 $N$의 순열 $P$가 주어진다. 길이 $N$의 순열이란, 1ドル$부터 $N$까지의 모든 정수를 한 번씩 사용하여 임의로 배열한 것을 말한다. 이때 다음을 만족하는 $(i, j)$ 쌍의 개수를 구하라.

• 1ドル \le i < j \le N$
• $\min(P_i, P_j) > \max(0,P_{i+1}, P_{i+2}, \cdots, P_{j-1})$

$P_i$는 $P$의 $i$번째 원소를 말한다.

입력

첫 번째 줄에 순열의 길이를 나타내는 정수 $N$이 주어진다.

두 번째 줄에 순열의 원소를 나타내는 $N$개의 정수 $P_1, P_2, \cdots, P_N$이 공백으로 구분되어 주어진다.

출력

문제의 답을 출력한다.

제한

• 1ドル \le N \le 200{,}000$

힌트