Wstęp do programowania w C++

Patryk jest pilnym uczniem i bardzo lubi matematykę. Właśnie przerabia dział kombinatoryki. Zadania kombinatoryczne dla Patryka są wyjątkowo łatwe i szybko je rozwiązuje, dlatego postanowił, że będzie sobie je utrudniał. Nauczyciel zadał właśnie pracę domową, polegającą na wyznaczeniu liczby permutacji danego zbioru (multizbioru). Natomast Patryk zastanawia się jaka jest najmniejsza liczba podmian liczb w tym n elementowym zbiorze/mutizbiorze, aby utrzymać dowolną permutację zbióru n elementowego złożonego ze zbioru liczb 1, 2, ..., n.

Wejście

W pierwszym wierszu jedna dodatnia całkowita liczba n określająca liczbę elementów w zbiorze/multizbiorze nie większa niż milion.

W drugim wierszu n dodatnich liczb całkowitych nie większych niż miliard. 

Wyjście

Jedna liczba naturalna określająca liczbę podmian.

Przykład

Wejście:
5
6 2 2 6 1

Wyjście:
3

Wyjaśnienie

Należy podmienić liczby np. 6 2 2 6 1 na np. 5 2 3 4 1.