C. Forest (A) - Egg
time limit per test
6 seconds
memory limit per test
32 megabytes
input
standard input
output
standard output

The memory limit for this problem is 4 MB.

In computer science, a tree is a connected graph with no cycles. Each node in a tree has exactly one parent, except for the root, which doesn't have a parent.

A forest is a graph that consists of one or more trees.

We introduce the following method to generate a forest of n nodes:

  • The input for the method is an array A of n distinct integers.
  • Edges are generated in the following way: the parent of node i is j, where j is the maximum index such that j < i and Aj > Ai. If such index doesn't exist, then node i has no parent.

Note that the generated trees are rooted.

Given an array of n distinct integers, find the number of trees in the forest generated using this array.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 2 × 106), the size of the array.

The second line contains n distinct integers A1, A2, ..., An (1 ≤ Ai ≤ n), representing the values of the array.

As the memory limit for this problem is 4 MB, you need to solve it without storing the array.

Output

Print a single integer that represents the number of trees in the generated forest.

Examples
Input
3
2 1 3
Output
2
Input
5
5 4 3 2 1
Output
1
Input
1
1
Output
1