WhiteRaptor cuối cùng đã tìm thấy đồng loại của mình tại TheRaptorLand! Không giống như WhiteRaptor bình thường, TheRaptorLand có nhiều loại raptor mang màu sắc khác nhau: PinkRaptor, BlueRaptor và GreenRaptor.
WhiteRaptor đã xếp tất cả $n$ con raptor ở TheRaptorLand thành một hàng, được đánh số từ 1 đến $n$ từ trái sang phải. Con raptor thứ $i$ từ trái sang có màu $c[i]$. Cậu ấy muốn chọn một số con raptor để giữ làm bạn trong tầng hầm của mình mãi mãi. Tuy nhiên, cậu ấy chỉ có thể làm điều đó bằng cách loại bỏ không hoặc nhiều con raptor từ hai đầu trái và phải của hàng, và giữ lại tất cả các con raptor còn lại.
Để đảm bảo không có con raptor nào còn lại bị cô lập, cậu ấy muốn hiệu số giữa tần suất của màu raptor phổ biến nhất và tần suất của màu raptor ít phổ biến nhất không vượt quá $k$. Lưu ý rằng nếu không còn con raptor nào của một màu nhất định, tần suất của màu raptor ít phổ biến nhất sẽ là 0.
Hãy giúp WhiteRaptor tìm số lượng raptor tối đa mà cậu ấy có thể giữ lại!
Dữ liệu vào
Chương trình của bạn phải đọc từ thiết bị nhập chuẩn.
Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $k$.
Dòng thứ hai của dữ liệu vào chứa $n$ số nguyên cách nhau bởi dấu cách $c[1], c[2], \dots, c[n]$.
Dữ liệu ra
Chương trình của bạn phải in ra thiết bị xuất chuẩn.
In ra một số nguyên duy nhất là số lượng raptor tối đa mà cậu ấy có thể giữ lại.
Nhiệm vụ con
Đối với tất cả các trường hợp kiểm thử, dữ liệu vào sẽ thỏa mãn các giới hạn sau:
- $1 \le n \le 200\,000$
- $0 \le k \le 200\,000$
- $1 \le c[i] \le 3$ với mọi $1 \le i \le n$
Chương trình của bạn sẽ được kiểm thử trên các bộ dữ liệu thỏa mãn các hạn chế sau:
| Nhiệm vụ con | Điểm | Các hạn chế bổ sung |
|---|---|---|
| 0 | 0 | Các bộ test mẫu |
| 1 | 5 | $n \le 500$ |
| 2 | 9 | $n \le 2000$ |
| 3 | 11 | $c[i] \le 2$ |
| 4 | 15 | $k = 0$ |
| 5 | 16 | Tồn tại $1 \le j \le n$ sao cho $c[i] \neq 3$ với mọi $i \le j$, và $c[i] = 3$ với mọi $i > j$ |
| 6 | 20 | Trong bất kỳ dãy liên tiếp nào có từ 3 con raptor trở lên, màu 3 là màu ít phổ biến nhất |
| 7 | 24 | Không có hạn chế bổ sung |
Ví dụ
Dữ liệu vào 1
11 2 2 2 1 2 1 3 2 1 2 1 1
Dữ liệu ra 1
7
Ghi chú
Trường hợp kiểm thử này hợp lệ cho các nhiệm vụ con 1, 2, 6 và 7.
Từ raptor thứ 3 đến raptor thứ 9, số lượng raptor có $c[i] = 1, 2$ và $3$ lần lượt là 3, 3 và 1. Vì hiệu số giữa tần suất lớn nhất và nhỏ nhất không vượt quá $k = 2$, tập hợp các raptor này thỏa mãn tiêu chí của WhiteRaptor.
Một ví dụ về tập hợp raptor không hợp lệ là từ raptor thứ 3 đến raptor thứ 10, vì việc thêm một con raptor nữa có $c[i] = 1$ khiến tần suất của màu phổ biến nhất trở thành 4. Hiệu số giữa tần suất lớn nhất và nhỏ nhất lúc này là 3, vượt quá $k = 2$.
Có thể chứng minh rằng 7 là số lượng raptor lớn nhất mà WhiteRaptor có thể giữ lại mà vẫn thỏa mãn tiêu chí của mình.
Dữ liệu vào 2
6 2 2 1 3 3 3 3
Dữ liệu ra 2
5
Ghi chú
Trường hợp kiểm thử này hợp lệ cho các nhiệm vụ con 1, 2, 5 và 7. WhiteRaptor nên chọn các raptor từ 1 đến 5.
Dữ liệu vào 3
7 0 1 2 1 2 1 2 1
Dữ liệu ra 3
0
Ghi chú
Trường hợp kiểm thử này hợp lệ cho tất cả các nhiệm vụ con. Vì bất kỳ dãy raptor liên tiếp nào cũng sẽ không chứa raptor có $c[i] = 3$, tần suất của màu ít phổ biến nhất sẽ luôn là 0. Điều này có nghĩa là WhiteRaptor không thể chọn bất kỳ dãy raptor không rỗng nào. Do đó, kết quả là 0.
Lưu ý rằng trường hợp kiểm thử này thỏa mãn nhiệm vụ con 5 vì chúng ta có thể gán $j = n$ (không có raptor màu 3 nào xuất hiện).