CSES - Towers | Tòa tháp

View as PDF
All submissions
Best submissions
Authors:
Flower_On_Stone , HoaiAnDeepTry , nguyendangquocthinh
Problem type
Points: 1200 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

You are given \(n\) cubes in a certain order, and your task is to build towers using them. Whenever two cubes are one on top of the other, the upper cube must be smaller than the lower cube.

You must process the cubes in the given order. You can always either place the cube on top of an existing tower, or begin a new tower. What is the minimum possible number of towers?

Input

  • The first input line contains an integer \(n\): the number of cubes.
  • The next line contains \(n\) integers \(k_1,k_2,\ldots,k_n\): the sizes of the cubes.

Output

  • Print one integer: the minimum number of towers.

Constraints

  • \(1 \leq n \leq 2 \cdot 10^5\)
  • \(1 \leq k_i \leq 10^9\)

Example

Sample input

5  
3 8 2 1 5

Sample output

2

Comments