A sequence of integers \(x_1, x_2, \dots, x_N\) is called beautiful if it can be split into contiguous subsequences such that

Each subsequence consists of at least 3 elements
\(x_i < x_l\) and \(x_i < x_r\) for every \(i (l < i < r)\) in contiguous subsequence \(x_l, x_{l + 1}, \dots, x_{r - 1}, x_r\).

For instance 7, 5, 3, 2, 6, 4, 1, 3, 5 is a beautiful sequence which can be split into [7,5,3,2,6] [4,1,3,5], but 7, 5, 3, 2, 4, 1, 3, 5 is not a beautiful sequence.

Given a sequence \(A_1, A_2, \dots, A_N\). Emil decided to find out the number of indices \(i\) such that the prefix sequence \(A_1, A_2, \dots, A_i\) is beautiful. This task is too hard for him, so he asks you to help.

Find out the number of beautiful prefix sequences.

Input format

The first line contains \(N\) denoting the length of the sequence.
The \(i'th\) of the next \(N\) lines contains \(A_i\).

Output format

The count of beautiful prefix sequences.

Constraints

\(1 \leq N \leq 10^5 \\ 1 \leq A_i \leq 10^5\)