Bedao Mini Contest 09 - CNTDIFF

View as PDF
Submit solution
Points: 0.30 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
bedao
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Chó Vàng đang đi ngang qua một dãy hoa tuyệt đẹp, tức cảnh sinh tình, Chó Vàng lại nhớ đến crush đã nửa ngày không gặp.

Anh muốn hái một vài bông và gom lại thành một bó hoa to để tặng crush của mình. Dãy hoa gồm ~n~ bông hoa với nhiều màu sắc sặc sỡ mọc thành một hàng, Chó Vàng chỉ được phép hái một đoạn bất kỳ gồm ~k~ bông hoa liên tiếp nhau.

Vẻ đẹp của bó hoa sẽ được tính bằng số lượng màu sắc khác nhau của những bông hoa thuộc bó hoa đó. Chó Vàng muốn dành tặng cho crush những thứ tốt đẹp nhất nhưng chưa biết chọn thế nào để được bó hoa đẹp nhất. Bạn hãy giúp Chó vàng nhé!

Input

  • Dòng đầu là hai số nguyên ~n~, ~k~ lần lượt là số lượng bông hoa trong dãy và số lượng hoa Chó Vàng được phép hái. ~(1 \le k \le n \le 3 \times 10^5)~

  • Dòng thứ hai là dãy số nguyên dương ~a_1, a_2, .., a_n~ lần lượt là vẻ đẹp của ~n~ bông hoa. ~(1 \le a_i \le 10^9)~

Output

  • Một số nguyên là vẻ đẹp của bó hoa đẹp nhất Chó Vàng có thể hái.

Sample Input

7 3
1 2 1 2 3 3 1

Sample Output

3

Note

  • Dãy ~3~ bông hoa liên tiếp có số lượng màu khác nhau nhiều nhất là ~[1, 2, 3]~.

Subtask

  • ~40\%~ số test có ~k \le n \le 100~

  • ~40\%~ số test khác có ~k \le n \le 10^4~

  • ~20\%~ số test còn lại không có điều kiện gì thêm

Comments

Please read the guidelines before commenting.