산

온조는 산 오르기를 좋아하는 등반가이다. 그래서 온조는 길이가 $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 \le N \le 500000$

각 $i$ ($1 \le i \le N$)에 대해, $1 \le A_i \le 1000000000$