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ể.

Nói cách khác, Alice muốn chọn một số chỉ số ~(i_1,i_2,\dots,i_k)~ ~(1 \le k \le N)~ sao cho:

• ~1 \le i_1 < i_2 < \dots < i_k \le N~.

• ~A_{i_1}=A_{i_2}=\dots=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 ~N \ge y > i_k~ mà ~A_y=A_{i_k}~.

• Giá trị ~D=\max(0,i_2-i_1,i_3-i_2,\dots,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 ra một viên gạch bất kì và thay đổi màu của nó thành một màu ~c~ tùy ý với ~1 \le c \le M~. Hãy tính giá trị ~D~ nhỏ nhất nếu như Alice có thể tùy ý thay đổi màu của tối đa một viên gạch bất kì.

Input

• 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 ~(1 \le N,M \le 2 \cdot 10^5)~.

• 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~ ~(1 \le A_i \le M)~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

• 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.

Scoring

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

Sample Input 1

6 2
1 2 2 1 2 1

Sample Output 1

1

Sample Input 2

5 2
1 2 2 1 2

Sample Output 2

0

Notes

• Ở ví dụ thứ nhất, 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~.

• Ở ví dụ thứ hai, 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~.