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.