Bedao Regular Contest 05 - CARRAY

Xem dạng PDF

Gửi bài giải


Điểm: 0,30 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

~Minh~ là một cậu bé khó tính. Cậu có sở thích sưu tầm những mảng số khác nhau.

Dạo gần đây, cậu ấy vừa nhặt được một mảng ~A~ gồm ~n~ số nguyên.

Minh không hài lòng với mảng ~A~ hiện tại. Cậu ấy sẽ tạo ra mảng ~B~ mới từ ~A~ bằng cách sau:

  • Đầu tiên, mảng ~B~ là mảng rỗng.
  • Lần lượt đi từ phần tử đầu tiên ~(A_1)~ cho đến phần tử cuối cùng ~(A_n)~. Tại lượt thứ ~i~, Minh sẽ thêm ~A_i~ vào đầu hoặc cuối của mảng ~B~.

Sau khi thực hiện thao tác trên, Minh sẽ được mảng ~B~ mới gồm ~n~ phần tử.

Minh muốn tạo mảng ~B~ sao cho độ dài của dãy con tăng ngặt tìm được trên ~B~ là lớn nhất. Hãy giúp Minh đạt được điều này.

Input

  • Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.
  • Dòng tiếp theo chứa ~n~ số nguyên ~A_1, A_2, \dots, A_n~ ~(|A_i| \le 10^9)~.

Output

  • Một số duy nhất là độ dài dãy con tăng ngặt dài nhất tìm được sau khi thay đổi dãy ~A~ bằng thao tác trên.

Sample Input

6
4 5 5 6 3 7

Sample Output

5

Subtask

  • ~40~% số test với ~1 \le n \le 20~.
  • ~30~% số test tiếp theo với ~1 \le n \le 1000~.
  • ~30~% số test còn lại không có ràng buộc gì thêm.

Note

Ở test mẫu đầu tiên, lần lượt thực hiện như sau:

  • Thêm số ~4~ vào mảng, mảng ~B~ trở thành ~[4]~.
  • Thêm số ~5~ vào cuối mảng, mảng ~B~ trở thành ~[4, 5]~.
  • Thêm số ~5~ vào cuối mảng, mảng ~B~ trở thành ~[4, 5, 5]~.
  • Thêm số ~6~ vào cuối mảng, mảng ~B~ trở thành ~[4, 5, 5, 6]~.
  • Thêm số ~3~ vào đầu mảng, mảng ~B~ trở thành ~[3, 4, 5, 5, 6]~.
  • Thêm số ~7~ vào cuối mảng, mảng ~B~ trở thành ~[3, 4, 5, 5, 6, 7]~.

Khi đó, dãy con tăng ngặt dài nhất là ~[3, 4, 5, 6, 7]~, với độ dài là ~5~.


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 10
    preVOI285  đã bình luận lúc 18, Tháng 4, 2022, 14:46

    bài này thực chất là bài này: https://oj.vnoi.info/problem/beadsnb

    nên trong contest có vài code chỉ cần copy code là ac thôi