Problem description

Jasio, przygotowując się do konkursów informatycznych, nauczył się ostatnio rozwiązywać problem LISa (longest incrementing subsequence), czyli zadanie, w którym dany jest ciąg liczb naturalnych i należy z niego wykreślić jak najmniej elementów, aby pozostałe elementy, czytane od lewej do prawej, tworzyły ciąg rosnący (czyli właśnie LIS). Przykładowo: dla ciągu wejściowego (2,7,5,4,6,3,10,7,15), LISem jest podciąg (2,4,6,10,15) (powstały po usunięciu elementów 7, 5, 3, 7).

Jasio nie poprzestaje, gdy nauczy się czegoś nowego. Wymyślił więc koncept dobrego LISa: jest to najdłuższy podciąg rosnący, w którym spełniony jest dodatkowy warunek: suma każdych dwóch jego sąsiednich elementów jest liczbą pierwszą. Dla naszego przykładowego wejściowego ciągu, dobrym LISem jest (2,5,6,7). Sumy sąsiednich elementów są w tym ciągu liczbami pierwszymi (2 + 5 = 7, 5 + 6 = 11, 6 + 7 = 13). Czy już wiesz jakie będzie zadanie?

Napisz program, który: wczyta ciąg wejściowy, wyznaczy jego dobry LIS i wypisze wynik na standardowe wyjście.

Dla uproszczenia: Możesz założyć, że ciąg wejściowy jest generowany w sposób pseudolosowy: dla każdego testu ustalana jest długość ciągu i wartość M, a potem każdy z N elementów generowanego ciągu jest losowany niezależnie z przedziału [1,M].

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca długość ciągu wejściowego. W drugim (ostatnim) wierszu wejścia znajduje się ciąg N liczb naturalnych A_i, pooddzielanych pojedynczymi odstępami. Są to kolejne elementy ciągu wejściowego.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba naturalna R, określająca długość dobrego LISa. W drugim (ostatnim) wierszu wyjścia powinien się znaleźć rosnący ciąg R liczb naturalnych pooddzielanych pojedynczymi odstępami – dobry LIS ciągu wejściowego.

Jeżeli istnieje wiele możliwych rozwiązań, Twój program może wypisać dowolne z nich.

Ograniczenia

1 ≤ N ≤ 200 000, 1 ≤ A_i ≤ 10⁹.

Przykład

9
2 7 5 4 6 3 10 7 15

4
2 5 6 7