405108: GYM101798 C Forest (A) - Egg

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 A_j > A_i. 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.

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

The second line contains n distinct integers A₁, A₂, ..., A_n (1 ≤ A_i ≤ 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.

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

3
2 1 3

2

5
5 4 3 2 1

1

1
1

1