A sequence of integers x1,x2,…,xN is called beautiful if it can be split into contiguous subsequences such that
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 A1,A2,…,AN. Emil decided to find out the number of indices i such that the prefix sequence A1,A2,…,Ai 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
Output format
The count of beautiful prefix sequences.
Constraints
1≤N≤1051≤Ai≤105
There are 2 beautiful prefix sequences [14,2,6],[14,2,6,3,9].