Towers

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

You receive $n$ cubes in a fixed order. A cube may be placed on an existing tower only if it is strictly smaller than the current top cube. Each cube must be processed immediately: place it on a tower or start a new tower. Find the minimum possible number of towers.

Input

The first line contains $n$.

The second line contains cube sizes $k_1,\ldots,k_n$.

Output

Print the minimum number of towers.

Subtasks

• Subtask 1 — 20%: $n\le1000$.
• Subtask 2 — 30%: $n\le50000$.
• Subtask 3 — 50%: $1\le n\le2\cdot10^5$, $1\le k_i\le10^9$.

Examples

Input

5
3 8 2 1 5

Output

2

Explanation

Two towers are sufficient, and the arrival order prevents using only one.