Bài 10.4. Chuỗi Tăng Trưởng Nhập Kho - [Độ khó: Khá]

Trong vai trò quản lý chuỗi cung ứng của một cửa hàng lớn, bạn thường xuyên phải theo dõi số lượng sản phẩm nhập kho hàng ngày. Để đánh giá hiệu suất của nhà cung cấp, bạn cần xác định "chuỗi tăng trưởng nhập kho" dài nhất. Một chuỗi tăng trưởng nhập kho là một dãy các ngày liên tiếp mà số lượng sản phẩm nhập kho vào mỗi ngày đều nghiêm ngặt lớn hơn ngày hôm trước. Bạn cần tìm độ dài của chuỗi tăng trưởng nhập kho dài nhất này.

INPUT FORMAT

Dòng đầu tiên chứa một số nguyên dương \(N\) (\(1 \le N \le 10^5\)), là số ngày bạn theo dõi. Dòng thứ hai chứa \(N\) số nguyên \(S_1, S_2, \dots, S_N\) (\(0 \le S_i \le 10^9\)), là số lượng sản phẩm nhập kho vào ngày thứ \(i\). Các số cách nhau bởi một dấu cách.

OUTPUT FORMAT

In ra một số nguyên duy nhất là độ dài của chuỗi tăng trưởng nhập kho dài nhất. Nếu không có chuỗi tăng trưởng nào (ví dụ, tất cả các ngày đều giảm hoặc bằng nhau), độ dài chuỗi tăng trưởng tối thiểu là 1 (vì mỗi ngày tự nó là một chuỗi tăng trưởng có độ dài 1).

Ví dụ 1:

Input:

8
10 12 15 14 16 18 19 17

Output:

4

Giải thích:

• Các chuỗi tăng trưởng:
  • 10, 12, 15 (độ dài 3)
  • 14, 16, 18, 19 (độ dài 4)
• Các chuỗi tăng trưởng khác có độ dài 1 hoặc 2:
  • 10 (1)
  • 12 (1)
  • 15 (1)
  • 14 (1)
  • 16 (1)
  • 18 (1)
  • 19 (1)
  • 17 (1)
  • 10, 12 (2)
  • 12, 15 (2)
  • 14, 16 (2)
  • 16, 18 (2)
  • 18, 19 (2)
• Chuỗi tăng trưởng dài nhất là 14, 16, 18, 19 với độ dài là 4.

Ví dụ 2:

Input:

5
5 5 5 5 5

Output:

1

Giải thích:

• Không có ngày nào có số lượng nhập kho tăng so với ngày hôm trước.
• Mỗi ngày tự nó là một chuỗi tăng trưởng độ dài 1. Do đó, độ dài lớn nhất là 1.

Ví dụ 3:

Input:

3
20 15 10

Output:

1

Giải thích:

• Tất cả các ngày đều giảm hoặc bằng. Không có chuỗi tăng trưởng.
• Độ dài lớn nhất là 1.