카드 팩 구매하기

$N$장의 카드가 한 줄로 진열되어 있다. 카드의 순서는 바꿀 수 없다.

다음 규칙을 모두 만족하면서 정확히 $M$개의 카드 팩을 만든다.

• 하나의 카드 팩은 좌우로 연속한 카드들로 구성된다.
• 모든 카드 팩에 들어 있는 카드 수는 서로 같다.
• 하나의 카드 팩 안에는 같은 종류의 카드가 두 장 이상 들어 있을 수 없다.
• 하나의 카드는 최대 하나의 카드 팩에만 속할 수 있다.

가격은 팩에 들어 있는 카드 수와 관계없이 일정하므로, 하나의 카드 팩에 들어 있는 카드 수가 최대가 되도록 구성하려 한다. 규칙을 모두 만족하면서 하나의 카드 팩에 넣을 수 있는 최대 카드 수를 구하라.

첫째 줄에 두 자연수 $N$과 $M$이 공백으로 구분되어 주어진다. $N$은 진열된 카드 수이고, $M$은 구매해야 할 카드 팩 수이다.

둘째 줄에 $N$개의 자연수 식별 번호가 공백으로 구분되어 주어진다. 가장 왼쪽 카드부터 가장 오른쪽 카드까지 실제 진열 순서대로 주어진다.

각 식별 번호는 $1$ 이상 $500000$ 이하이다.

규칙을 모두 만족하면서 하나의 카드 팩에 구성할 수 있는 최대 카드 수를 한 줄에 출력한다. $M$개의 팩을 만들 수 없으면 $0$을 출력한다.

세 번째 샘플은 Small subtask에서는 나오지 않는다.