LIS again

A numeric sequence of ai is ordered if $a_1 < a_2 < \ldots < a_N$. Let the subsequence of the given numeric sequence ($a_1, a_2, \ldots , a_N$) be any sequence ($a_{i_1}, a_{i_2}, \ldots , a_{i_K}$), where $1 \leq i_1 < i_2 < \ldots < i_K \leq N$. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, eg. (1, 7), (3, 4, 8) and many others.
S[ i , j ] indicates ( $a_i, a_{i+1}, a_{i+2}, \ldots, a_j$) .
Your program, when given the numeric sequence ($a_1, a_2, \ldots , a_N$), must find the number of pair ( i, j) which makes the length of the longest ordered subsequence of S[ i , j ] equals to the length of the longest ordered subsequence of ($a_1, a_2, \ldots , a_N$).

Multi test cases (about 100), every case occupies two lines, the first line contain n, then second line contain n numbers $a_1, a_2, \ldots , a_N$ separated by exact one space.
Process to the end of file.

[Technical Specification]
$1 \leq n \leq 100000$
$0 \leq a_i \leq 1000000000$

For each case，.output the answer in a single line.

3
1 2 3
2
2 1

1
3

BestCoder Round #21