Tomorrow is a big day for Talb. In order to be accepted into competing alongside the greatest in the world for the Big Ino, he has to pass a small stage called Ijo. Now, he has been preparing for this stage for the last months and he knows all the tricks. However, being his first time there, he can't seem to be able to control his nerves.
He has some fancy machine which records how frequently he gets panic attacks and he wishes to use it in order to calm down.
The way the machine works is it provides a sequence a of N integers, separated by spaces, where ai represents Talb's degree of calmness. A panic attack taking place at time i has the shape of a subsequence of a, where:
Your task is to count the number of panic attacks Talb has, given such a sequence.
Note: You will receive full feedback for your submissions.
The first line contains N.
The second line contains the values of a.
A single integer - the number of panic attacks.
- 1 ≤ N ≤ 105
1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1
|1||The entire array is one great panic attack.|