Alice là một cô bé rất thích các màu sắc. Một hôm cô đang lang thang trên các con phố của TP HCM thì gặp một con đường gạch dài gồm \(N\) viên gạch liên tiếp, đánh số từ \(1\) đến \(N\), viên gạch thứ \(i\) có màu là một số nguyên dương \(A_i \le M\).

Cô muốn đi qua con đường này bằng cách: chọn một màu \(t\), sau đó bắt đầu đi từ viên gạch đầu tiên có màu \(t\), chỉ được bước sang các viên gạch có màu \(t\) kế tiếp và kết thúc lộ trình ở viên gạch cuối cùng có màu \(t\). Vì các viên gạch có màu \(t\) có thể không nằm liền tiếp nhau mà có thể nằm cách nhau một khoảng và việc đi một bước quá dài có thể khiến Alice vấp ngã, nên Alice muốn chọn một lộ trình sao cho khoảng cách giữa hai viên gạch liên tiếp mà cô đi là nhỏ nhất có thể.

Mục tiêu

Alice muốn chọn một số chỉ số \((i_1, i_2, ..., i_k)\) sao cho:

• \(1 \le i_1 < i_2 < ... < i_k \le N\)
• \(A_{i_1} = A_{i_2} = ... = A_{i_k}\)
• Không tồn tại \(1 \le x < i_1\) mà \(A_x = A_{i_1}\)
• Không tồn tại \(i_k \lt y \le N\) mà \(A_y = A_{i_k}\)
• Giá trị \(D = max(0, i_2 - i_1, i_3 - i_2, ..., i_k - i_{k-1})\) là nhỏ nhất có thể.

Yêu cầu

Biết rằng Alice được phép chọn một viên gạch bất kỳ và thay đổi màu của nó thành một màu \(c\) tuỳ ý với \(1 \le c \le M\). Hãy tính giá trị \(D\) nhỏ nhất nếu Alice có thể tuỳ ý thay đổi màu của tối đa một viên gạch bất kỳ.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương \(N\), \(M\) thể hiện số lượng viên gạch và số lượng màu.
• Dòng thứ hai chứa \(N\) số nguyên dương. Số thứ \(i\) là giá trị \(A_i\), thể hiện màu của viên gạch thứ \(i\).

Dữ liệu ra

• Một số nguyên duy nhất thể hiện giá trị \(D\) nhỏ nhất nếu Alice có thể đổi màu của tối đa một viên gạch.

Input 1

6 2
1 2 2 1 2 1

Output 1

1

Giải thích

• Alice đổi màu viên gạch thứ 4 thành màu 2.
• Sau đó chọn các chỉ số \((2,3,4,5)\) với cùng màu 2 cho khoảng cách của bước lớn nhất là 1.

Input 2

5 2
1 2 2 1 2

Output 2

0

Giải thích

• Alice đổi màu viên gạch thứ 4 thành màu 2.
• Sau đó chỉ cần chọn một chỉ số \((1)\) với màu 1 và không phải bước thêm. Khoảng cách của bước lớn nhất là 0.

Subtasks

Mỗi subtask bao gồm nhiều test đơn, điểm của thí sinh được tính theo từng test đơn:

• Subtask 1 (30%): \(N \le 100; M \le 3\)
• Subtask 2 (30%): \(N, M \le 100\)
• Subtask 3 (30%): \(A_i = (i \mod M) + 1\) với \(i = 1, 2, ..., N\)
• Subtask 4 (10%): Không có ràng buộc nào thêm.