산

온조는 산 오르는 것을 좋아하는 등반가이다. 그래서 온조는 길이가 $N$인 수열 $A_1, \cdots, A_N$에서 산 모양을 최대한 많이 찾으려고 한다.

만약 $A$의 부분수열 $A_l, \cdots, A_r (l \le r)$에 대해서, 어떤 정수 $l \le k \le r$가 존재하여 $A_l \le A_{l+1} \le \cdots \le A_k \ge \cdots \ge A_{r-1} \ge A_r$을 만족한다면 이 부분수열이 산 모양이라고 하자.

온조를 도와 수열 $A$가 주어지면 $A$의 부분수열 중 산 모양인 것의 개수를 구하여라.

첫째 줄에 수열 $A$의 길이 $N$이 주어진다.

둘째 줄에 $N$개의 정수 $A_1, \cdots, A_N$이 공백을 사이에 두고 주어진다.

첫째 줄에 $A$의 부분수열 중 산 모양인 것의 개수를 출력하라.

• $1 ≤ N ≤ 500\ 000$
• 각 $i (1 \le i \le N)$에 대해, $1 \le A_i \le 1\ 000\ 000\ 000$