Hide

Problem A
Tower Construction

/problems/tornbygge/file/statement/en/img-0001.png
Towers corresponding to Sample $1$

Kim’s current obsession is to build towers from ordered sequences of Lego bricks. The towers are built one at a time, brick by brick. The first available brick is the base of the first tower. If the next available brick is wider than the top of the current tower, we say that the current tower is finished and make the brick the base of a new tower. Otherwise, the brick is placed (in an arbitrary fashion) on top of the current tower.

Given the ordering and widths of the bricks, how many towers is Kim going to build?

Input

An integer $N$ with $1 \leq N \leq 10^5$, followed by a line consisting of $N$ integers $x_ i$, where $1 \leq x_ i \leq 10^6$, corresponding to the width of the bricks in the order they are available.

Output

A single integer, the number of resulting towers.

Sample Input 1 Sample Output 1
10
4 3 3 2 1 2 2 1 1 3
3
Sample Input 2 Sample Output 2
5
2 2 2 2 2
1

Please log in to submit a solution to this problem

Log in