Annihilation-Kanone#11727
Im Link-Cut-System gibt es Planeten, jeder mit seinem eigenen Typ. Der Typ eines Planeten ist eine ganze Zahl, die von bis reicht. Ihnen wird ein Array von ganzen Zahlen a_1, a_2, \dots, a_n gegeben, das die Typen jedes Planeten darstellt. Ihr Ziel ist es, alle Planeten auf denselben Typ zu bringen oder festzustellen, dass dies unmöglich ist.
Um dies zu erreichen, hat Lucy eine Anihilatorkanone für Sie konstruiert, die die Typen jedes Planeten in einem Einsatz in jeden anderen Typ (von bis ) ändern kann, der nicht gleich ihrem vorherigen Typ ist. Die neuen Typen der Planeten müssen nicht unbedingt unterschiedlich sein.
Formell können Sie bei einem Schuss der Kanone ein Array x_1, x_2, \dots, x_n von ganzen Zahlen aus bis erstellen, sodass x_i \neq a_i für alle , und dann jedem Element des Arrays a_i einen neuen Wert x_i zuweisen.
Da die Verwendung der Annihilation-Kanone ziemlich ressourcenintensiv ist und Sie Ressourcen für die Erfassung des bösen Chmyaaax sparen müssen, müssen Sie das Ziel mit der minimalen Anzahl von Einsätzen der Waffe erreichen. Ihre Aufgabe ist es, diese Anzahl zu bestimmen oder festzustellen, dass es unmöglich ist, alle Planeten auf einen Typ zu bringen.
Die erste Zeile enthält zwei ganze Zahlen und (1 \le n, k \le 10^5) — die Anzahl der Planeten und die Anzahl der möglichen Typen für jeden Planeten.
Die zweite Zeile enthält ganze Zahlen a_1, a_2, \dots, a_n (1 \le a_i \le k) — die Typen der Planeten.
In einer einzigen Zeile müssen Sie die minimale Anzahl von Einsätzen der Annihilator-Waffe ausgeben, die erforderlich sind, um alle Planeten auf denselben Typ zu bringen, oder , wenn es unmöglich ist.
Beispiel
Beispiel 1
Beispiel 2
Beispiel 3
Im ersten Beispiel können Sie den einzigen Einsatz der Waffe durchführen und die Typen beider Planeten auf ändern. Da ihre ursprünglichen Typen unterschiedlich sind, kann die Antwort nicht sein.
Im zweiten Beispiel kann gezeigt werden, dass es nicht möglich ist, beide Planeten auf denselben Typ zu bringen.
Im dritten Beispiel haben alle Planeten anfänglich denselben Typ, sodass Sie nichts tun müssen.
Im vierten Beispiel können Sie die Waffe zweimal verwenden:
[1, 2, 3, 1] - [2, 3, 2, 3]
[2, 3, 2, 3] - [1, 1, 1, 1]
Es kann gezeigt werden, dass die Bedingung nicht in einem Einsatz der Waffe erfüllt werden kann.
( Punkte): n = 1;
( Punkte): k = 1;
( Punkte): n = 2;
( Punkte): k = 2;
( Punkte): n \le 100,\,k \le 100;
( Punkte): keine zusätzlichen Einschränkungen.