Svi smo nekada imali problema pripamćenju brojeva telefona, datuma rođenja, šifri... Sličan problem ima inajbogatiji patak na svetu, stari Baja. Naime, Baja je za svoj rođendan od Prokepronalazača dobio sef najnovije generacije. Kako je Proka primetio da Baji polakopopušta pamćenje, šifru mu je zapisao na papiru. Međutim, svestan stalnih napadaopake braće Buldog i opasnosti koja vreba ukoliko se oni domognu tog papira, Baja jemalo kodirao šifru. Vaš zadatak je da pomognete Baji da što pre nađe dužinunjegove šifre kao i broj mogućih kombinacija.

Šifra predstavlja najduži uzastopni podniz koji čini permutacijubrojeva nekog segmenta [a, b] (uzastopni elementi niza koji činepermutaciju).

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza)U prvom redu nalazi se broj n, kojipredstavlja broj elemenenata niza. U svakom od sledećih n redova,nalazi se po jedan broj. Dati niz predstavlja brojeve ispisane naBajinom papiru.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz)U prvim i jedini red ispisati dva brojaodvojena razmakom: dužinu najdužeg uzastopnog podžniza koji jepermutacija i broj mogućnosti.

Ograničenja:

• 1 ≤ n ≤ 5000
• elementi niza su pozitivni celi brojevi manji od 2³⁰
• vremensko ograničenja za izvršavanje programa je 1 s
• memorijsko ograničenje za izvršavanje programa je 32 MB

Primer 1:

6
2
8
6
7
5
1

4 1

Primer 2:

6
1
3
2
1
2
3

3 3

Na slici su prikazana rešenja primera 1 i 2.

U prvom primeru uslov permutacije zadovoljavaju podnizovi (2), (8), (8,6,7), (6), (6,7),(6,7,5), (7), (5) i (1), ali oni nemaju maksimalnu dužinu (koja je u tom primeru 4).

U drugom primeru, tri podniza čine moguća rešenja.