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\)