Đoạn Dài Nhất Có Không Quá K Giá Trị · canuc80k0633

Cho mảng $a$ gồm $n$ số nguyên. Một đoạn liên tiếp được gọi là hợp lệ nếu trong đoạn có không quá $k$ giá trị khác nhau.

Hãy in hai đầu mút của một đoạn hợp lệ dài nhất. Nếu có nhiều đoạn dài nhất, in bất kỳ một đoạn nào.

Input

Dòng đầu chứa hai số nguyên $n$ và $k$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Output

In hai số nguyên $l$ $r (1 \leq l \leq r \leq n)$ là hai đầu mút của một đoạn dài nhất, theo chỉ số bắt đầu từ $1$ .

Constraints

$1 \leq k \leq n \leq 5 \cdot 1 0^{5}$ .
$0 \leq a_{i} \leq 1 0^{6}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 2000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

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

Output

4 8

Giải thích: Đoạn $a_{4}, \dots, a_{8} = [3, 4, 3, 3, 4]$ dài $5$ và chỉ có hai giá trị khác nhau. Mọi đoạn dài hơn đều chứa ít nhất ba giá trị khác nhau.

Phân tích: Duy trì cửa sổ [l,r], tần suất từng giá trị và số lượng giá trị khác nhau. Khi thêm a_r làm số loại vượt k, tăng l và giảm tần suất cho tới khi cửa sổ hợp lệ trở lại. Sau mỗi bước, cập nhật đoạn dài nhất.
Chứng minh đúng: Sau vòng co, [l,r] là cửa sổ dài nhất kết thúc tại r mà có không quá k loại; mọi đầu trái nhỏ hơn đều không hợp lệ. Mọi đoạn tối ưu có một biên phải nào đó, nên khi biên phải ấy được xét, thuật toán ghi nhận một đoạn dài ít nhất bằng nó. Đoạn được in luôn hợp lệ, do đó là tối ưu.
Độ phức tạp: Thời gian O(n) và bộ nhớ O(10^6+n).