EGOI năm nay được tổ chức tại Bonn. Ban tổ chức muốn phát tối đa một hộp quà cho mỗi đội tham dự cuộc thi, trong đó mỗi đội được biểu diễn bằng một số từ ~0~ đến ~T-1~. Các thí sinh đang đứng thành một hàng. Tuy nhiên, họ đứng xen kẽ nhau nên những người thuộc cùng một đội có thể không đứng cạnh nhau. Lưu ý rằng có ít nhất một đội có nhiều hơn một người trong hàng. Có ~N~ người trong hàng. Người thứ ~i~ thuộc đội ~a_i~. Vấn đề đặt ra là: mỗi đội chỉ được nhận tối đa một hộp quà. Để quá trình phát quà diễn ra suôn sẻ, đồng thời chấp nhận việc một số đội có thể không nhận được quà, ban tổ chức muốn tạm dừng việc phát quà đúng một lần, bỏ qua một số thí sinh rồi tiếp tục phát các hộp quà. Nói cách khác, họ sẽ bỏ qua một đoạn liên tiếp ~[\ell,r]~ trong hàng thí sinh.

Không nhất thiết mọi đội đều phải nhận được quà. Tuy vậy, ban tổ chức muốn tối đa hóa số đội nhận được quà, đồng thời bảo đảm không đội nào nhận được từ hai phần quà trở lên. Điều này tương đương với việc tối thiểu hóa số thí sinh bị bỏ qua khi tuân thủ điều kiện trên. Hãy giúp ban tổ chức quyết định thời điểm thích hợp nhất để tạm dừng và tiếp tục phát quà sao cho số thí sinh bị bỏ qua là ít nhất có thể.

Input

Dòng đầu tiên chứa hai số nguyên ~T~ và ~N~ — số đội và số thí sinh trong hàng.

Dòng thứ hai chứa ~N~ số nguyên ~a_i~, trong đó số nguyên thứ ~i~ cho biết người ở vị trí ~i~ trong hàng thuộc đội nào. Bảo đảm rằng mỗi số nguyên từ ~0~ đến ~T-1~ đều xuất hiện ít nhất một lần.

Output

In ra hai số nguyên ~\ell~ và ~r~, trong đó ~\ell~ là chỉ số của người đầu tiên bị bỏ qua và ~r~ là chỉ số của người cuối cùng bị bỏ qua. Lưu ý rằng ~\ell~ và ~r~ được đánh chỉ số từ ~0~ đến ~N-1~. Nếu có nhiều phương án, hãy in ra một phương án bất kỳ.

Scoring

• ~1 \le T < N \le 500000~.

• ~0 \le a_i \le T-1~.

Lời giải của bạn sẽ được kiểm tra trên một số nhóm test, mỗi nhóm có một số điểm nhất định. Mỗi nhóm test chứa một tập hợp các test. Để nhận được điểm của một nhóm test, bạn cần giải đúng tất cả các test trong nhóm đó.

Subtask	Điểm	Ràng buộc
1	~8~	~N=T+1~, tức là chỉ có một đội xuất hiện hai lần
2	~11~	~N=2 \cdot T~ và mỗi đội xuất hiện đúng một lần trong nửa đầu và đúng một lần trong nửa sau của hàng
3	~14~	~1 \le T < N \le 500~
4	~21~	~N=2 \cdot T~ và mỗi đội xuất hiện hai lần
5	~22~	~1 \le T < N \le 5000~
6	~24~	Không có giới hạn gì thêm

Sample Input 1

4 5
1 3 0 2 3

Sample Output 1

1 1

Sample Input 2

3 6
1 0 2 2 1 0

Sample Output 2

0 2

Sample Input 3

4 8
0 2 0 1 2 1 3 3

Sample Output 3

2 6

Sample Input 4

3 6
1 1 2 0 1 0

Sample Output 4

0 3

Sample Input 5

4 6
0 1 2 0 3 2

Sample Output 5

2 3

Sample Input 6

5 13
3 3 3 1 2 0 3 3 2 1 4 1 0

Sample Output 6

1 9

Notes

Ví dụ thứ nhất thỏa mãn ràng buộc của các nhóm test ~1~, ~3~, ~5~ và ~6~. Có hai kết quả đầu ra khác nhau có thể được chấp nhận: 1 1 tương ứng với đường màu xanh lam liền nét và 4 4 tương ứng với đường chấm màu đỏ trong hình minh họa của đề gốc. Với cả hai cách, cả bốn đội đều nhận được quà và không đội nào nhận nhiều hơn một phần quà.

Ví dụ thứ hai thỏa mãn ràng buộc của các nhóm test ~2~, ~3~, ~4~, ~5~ và ~6~. Một lần nữa, có hai kết quả đầu ra khác nhau có thể được chấp nhận: 0 2 và 3 5, như trong hình minh họa của đề gốc. Trong cả hai trường hợp, cả ba đội đều nhận được quà.

Ví dụ thứ ba thỏa mãn ràng buộc của các nhóm test ~3~, ~4~, ~5~, ~6~. Phương án tối ưu là có ba đội nhận được quà, như trong hình minh họa của đề gốc. Các thí sinh có chỉ số ~0~, ~1~ và ~7~, lần lượt thuộc các đội ~0~, ~2~ và ~3~, nhận được quà. Đây là phương án duy nhất có thể.

Ví dụ thứ tư thỏa mãn ràng buộc của các nhóm test ~3~, ~5~ và ~6~. Một lần nữa, có hai kết quả đầu ra khác nhau có thể được chấp nhận: 0 3 và 1 4, như trong hình minh họa của đề gốc. Trong cả hai trường hợp, có đúng hai đội (đội ~0~ và đội ~1~) nhận được quà. Đội ~2~ không nhận được quà vì nếu phát quà cho đội này thì sẽ phải phát hai phần quà cho đội ~0~ hoặc đội ~1~, điều bị nghiêm cấm.

Ví dụ thứ năm thỏa mãn ràng buộc của các nhóm test ~3~, ~5~ và ~6~. Đáp án duy nhất có thể là 2 3, như trong hình minh họa của đề gốc. Cả bốn đội đều nhận được quà.

Ví dụ thứ sáu thỏa mãn ràng buộc của các nhóm test ~3~, ~5~ và ~6~. Tối đa bốn trong số năm đội có thể nhận được quà, như trong hình minh họa của đề gốc. Các thí sinh có chỉ số ~0~, ~10~, ~11~ và ~12~, lần lượt thuộc các đội ~3~, ~4~, ~1~ và ~0~, nhận được quà. Đây là phương án duy nhất có thể.

Ghi công và giấy phép

Bài toán này có nguồn gốc từ EGOI 2025 (Olympic Tin học nữ châu Âu), Ngày 1, được tổ chức tại Bonn, Đức.

• Đề bài gốc: Gift Boxes

• Tác giả: Anja Dožić.

• Chủ sở hữu bản quyền: Olympic Tin học nữ châu Âu 2025.

• Tài liệu chính thức: Đề bài và lời giải · Dữ liệu kiểm thử, trình chấm và các bản dịch

• Giấy phép: Creative Commons Ghi công – Chia sẻ tương tự (CC BY-SA), theo siêu dữ liệu chính thức của bài toán. Siêu dữ liệu không chỉ rõ phiên bản giấy phép.

• Các thay đổi: Dịch sang tiếng Việt và định dạng lại cho ClueOJ.

Bản dịch này được phân phối theo cùng các điều khoản CC BY-SA áp dụng cho bài toán gốc.

ClueOJ không có quan hệ liên kết với EGOI hoặc ban tổ chức EGOI 2025, cũng không được các bên này chứng thực.