Bedao Mini Contest 15 - 2SEG

View as PDF

Submit solution


Points: 0.65 (partial)
Time limit: 2.0s
Memory limit: 512M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Vì Alice đang rất bận nên Alice sẽ đố nhanh Bob một bài toán khá dễ thôi.

Cho một mảng ~a~ gồm ~n~ phần tử nguyên dương, hãy tìm ra ~2~ dãy con liên tiếp (có thể rỗng) của dãy ~a~ sao cho nếu ta gộp ~2~ dãy lại thì ta được một dãy mới có các phần tử phân biệt, đồng thời có nhiều phần tử nhất.

Input

  • Dòng đầu tiên nhập ~T~ ~(1 \le T \le 10)~ - số lượng bộ câu hỏi của Alice.

  • Nhóm dòng thứ ~i~ trong ~T~ nhóm dòng tiếp theo sẽ có dạng:

    • Dòng đầu tiên gồm một số nguyên dương ~n~.

    • Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~.

Output

  • In ra ~T~ dòng, trong đó dòng thứ ~i~ là độ dài lớn nhất hai dãy con tìm được của hỏi thứ ~i~.

Subtask

Gọi ~N~ là tổng các ~n~ trong tất cả các bộ câu hỏi.

  • ~20\%~ số test có ~1 \le a_i, N \le 200~.

  • ~40\%~ số test khác có ~1 \le a_i \le 20~ và ~1 \le N \le 10^6~.

  • ~40\%~ số test còn lại có ~1 \le a_i \le 10^5~ và ~1 \le N \le 5000~.

Sample Input 1

2
5
2 3 1 2 3
5
2 3 2 1 4

Sample Output 1

3
4

Comments

Please read the guidelines before commenting.


There are no comments at the moment.