Problem description

Jasio poznał ostatnio wiele różnych ciekawych metod na sortowanie ciągu liczb takich jak sortowanie przez scalanie, sortowanie bąbelkowe albo sortowanie przez zliczanie.

Zainspirowany tą tematyką postanowił wymyślić swój własny algorytm sortujący, który ma jednak parę wad i ograniczeń.

Ciągi, których sortowanie rozważa Jasio składają z liczb całkowitych o wartościach A_i z przedziału [0, 2^K) zapisanych na dokładnie k bitach. Algorytm Jasia pozwala na wykonywanie dowolnie wiele razy następującej operacji:

• Wybierz niepusty spójny fragment ciągu od l-tej do r-tej pozycji włącznie i każdej liczbie A_i (l ≤ i ≤ r) zamień wszystkie bity na przeciwne (zamień A_i na A_i ⊕ (2^K−1)).

Twoim zadaniem jest napisać program, który obliczy jaka jest minimalna liczba operacji konieczna do posortowania ciągu niemalejąco, albo wypisze, że nie jest to możliwe.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N i K oznaczające długość ciągu oraz liczbę bitów, za pomocą których da się zapisać wszystkie elementy ciągu.

W drugim wierszu wejścia znajduje się N liczb całkowitych pooddzielanych pojedynczymi odstępami oznaczających kolejne elementy ciągu A_i.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć się minimalna liczba operacji potrzebna do tego, żeby ciąg stał się niemalejący, albo jedna liczba -1 jeżeli posortowanie nie jest możliwe.

Ograniczenia

1 ≤ N ≤ 500 000, 1 ≤ K ≤ 20.

Przykład

4 3
5 2 4 1

2

7 2
0 1 0 1 0 1 0

-1