Nieatakujące się skoczki

Limit pamięci: 32 MB

Skoczek jest figurą, która atakuje pola na szachownicy zgodnie z poniższym rysunkiem (skoczek umieszczony w polu atakuje pola oznaczone przez krzyżyk).

Dana jest szachownica o rozmiarach — mająca wiersze i kolumn, gdzie — oraz zbiór pól na tej szachownicy. Wiersze na szachownicy są ponumerowane od góry do dołu liczbami od do , a kolumny od lewej do prawej liczbami od do .

Na szachownicy wolno rozmieszczać skoczki tylko na polach nie należących do oraz tak, aby żadne dwa nie atakowały się nawzajem. Zakładamy, że w każdej kolumnie co najwyżej jedno pole należy do . Zbiór można więc opisać w postaci ciągu: , gdzie . Wartość oznacza, że żadne pole w -tej kolumnie nie należy do , zaś wartość jest numerem wiersza jedynego pola w tej kolumnie, które należy do .

Zadanie

Ułóż program, który:

• wczytuje ze standardowego wejścia liczbę kolumn na szachownicy oraz opis zbioru pól ,
• znajduje maksymalną liczbę skoczków , które można ustawić na szachownicy zgodnie z podanymi zasadami oraz liczbę wszystkich takich ustawień skoczków,
• zapisuje wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita dodatnia , . Jest to liczba kolumn szachownicy. W każdym z kolejnych wierszy jest zapisana jedna liczba ze zbioru . Są to kolejne wyrazy ciągu będącego opisem zbioru pól .

Wyjście

Na standardowe wyjście należy zapisać dwie liczby całkowite i oddzielone odstępem.

Przykład

Dla danych wejściowych:

2
1
0

poprawną odpowiedzią jest:

4 2

Autor zadania: Wojciech Rytter.