Given an array $A$ of length $N$. We say that a subarray $(A_l, A_{l + 1}, \dots, A_r)$ is good if for every $l \le i < j < k \le r$ we can form a triangle (possible degenerate) with lengths $A_i, A_j, A_k$. In particular if $0 \le r - l \le 1$ then the subarray is good. Count the number of good subarrays. 

$\textbf{Input}$

The first line contains one integer - $n$ $(1 \le n \le 2 \cdot 10^5)$.

The second line contains $n$ integers - $A_1, A_2, \dots, A_N$ $(1 \le A_i \le 10^9)$.

$\textbf{Output}$

Output the number of good subarrays.