CSES - Towers | Tòa tháp

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Flower_On_Stone , HoaiAnDeepTry , nguyendangquocthinh
Dạng bài
Điểm: 1200 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn được cho \(n\) khối lập phương theo một thứ tự nhất định, và nhiệm vụ của bạn là xây dựng các tòa tháp bằng cách sử dụng chúng. Bất cứ khi nào hai khối lập phương nằm chồng lên nhau, khối lập phương phía trên phải nhỏ hơn khối lập phương dưới.

Bạn phải xử lý các khối phương theo thứ tự được cho. Bạn luôn có thể đặt khối lập phương lên trên đỉnh của một tòa tháp hiện có hoặc bắt đầu một tòa tháp mới. Số lượng tòa tháp tối thiểu có thể là bao nhiêu?

Input

  • Dòng đầu vào đầu tiên chứa một số nguyên \(n\): số lượng khối lập phương.
  • Dòng tiếp theo chứa \(n\) số nguyên \(k_1,k_2,\ldots,k_n\): kích thước của các khối lập phương.

Output

  • In một số nguyên: số lượng tòa tháp tối thiểu.

Constraints

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

Example

Sample input

5
3 8 2 1 5

Sample output

2

Bình luận