Podział naszyjnika

Limit pamięci: 128 MB

Mamy naszyjnik złożony z koralików, z których każdy jest jednego z rodzajów. Koraliki numerujemy liczbami całkowitymi od do . Koralik o numerze sąsiaduje w naszyjniku z koralikami o numerach oraz (o ile koraliki o takich numerach istnieją), a ponadto koraliki o numerach oraz również sąsiadują ze sobą. Chcemy podzielić naszyjnik dwoma cięciami na dwie niepuste części tak, aby każdy rodzaj koralika występował dokładnie w jednej z części (tzn. jeśli jedna z części zawiera koralik rodzaju , to druga część nie może zawierać żadnego koralika rodzaju ). Na ile sposobów możemy to zrobić oraz jaka jest minimalna różnica długości otrzymanych części?

Wejście

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite i () oddzielone pojedynczym odstępem, oznaczające długość naszyjnika i liczbę rodzajów koralików. Rodzaje koralików numerujemy liczbami od 1 do . Drugi wiersz wejścia zawiera ciąg liczb całkowitych () pooddzielanych pojedynczymi odstępami; liczba oznacza rodzaj koralika o numerze . Możesz założyć, że każdy rodzaj koralika wystąpi w naszyjniku co najmniej raz.

W testach wartych łącznie punktów zachodzi dodatkowy warunek .

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać dwie liczby całkowite oddzielone pojedynczym odstępem. Pierwsza z nich ma oznaczać liczbę sposobów, na jakie można podzielić naszyjnik (możesz założyć, że dla danych wejściowych co najmniej jeden podział jest możliwy). Druga liczba ma oznaczać minimalną różnicę długości otrzymanych części.

Przykład

Dla danych wejściowych:

9 5
2 5 3 2 2 4 1 1 3

poprawną odpowiedzią jest:

4 3

Wyjaśnienie do przykładu: Są cztery możliwe podziały; krótsza część może zawierać koraliki , , lub . W ostatnim przypadku uzyskujemy optymalną różnicę długości .

Testy "ocen":

• 1ocen: krótki naszyjnik z dwoma możliwymi podziałami ();
• 2ocen: naszyjnik długości , wszystkie koraliki mają różne kolory, wszystkie podziały są poprawne;
• 3ocen: , , naszyjnik postaci .

Autor zadania: Jacek Tomasiewicz.