Sticks

Interview

Time limit1sMemory limit512 MB

Summary

Given the heights of N sticks in a row, count how many sticks are visible when the row is viewed from the right, where a stick is visible only if it is strictly taller than every stick to its right.

Level: Easy3 of 10
Topics: Array, Implementation, Stack, Two pointers
Solved: No attempts yet

Problem

As in the figure below, sticks that differ only in height (some sticks may have the same height) and have the same shape are placed in a row, then numbered in order from the left. The heights of the sticks are 6, 9, 7, 6, 4, 6 in order, as shown in the figure. When the row of sticks is viewed from the right, some sticks are visible and some are not. That is, a stick is visible if it is behind the currently visible stick and is taller. For example, in the case shown in the figure, 3 sticks (number 6, number 3, number 2) are visible.

Given the height information of N sticks, write a program that determines how many are visible when viewed from the right.

Input

The first line contains an integer N (2 ≤ N ≤ 100,000), the number of sticks. Each of the following N lines contains an integer h (1 ≤ h ≤ 100,000), the height of a stick.

Output

Print the number of visible sticks when the N sticks are viewed from the right.

Examples2

Example 1
Input
```
6
6
9
7
6
4
6
```
Expected output
```
3
```
Example 2
Input
```
5
5
4
3
2
1
```
Expected output
```
5
```