시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB32720116865.882%

문제

길이 $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$

예제 입력 1

5
4 2 3 1 5

예제 출력 1

7

예제 입력 2

4
3 2 1 4

예제 출력 2

5

예제 입력 3

2
2 1

예제 출력 3

1