3. Aktuálny zoznam prianí

Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš, koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a skús sa pozrieť ako by mal vyzerať ideálny program. Ak zaťiaľ programovať nevieš, ale chcel/a by si vedieť možeš skúsiť náš python tutoriál.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Merlinovi na email [email protected]

Čas Vianoc sa blíži a preto už je najvyšší čas napísať si zoznam darčekov! Merlin si teda sadol a začal písať. Napísal si \(n\) darčekov, ktoré by veľmi chcel niekedy na Vianoce dostať. Keďže to je ale huncút, skopíroval ho za seba až \(n\)-krát (pre istotu, nech sa niektorý darček náhodou neprehliadne). Nanešťastie bolo týchto darčekov strašne veľa, a tak sa Merlinovi rodičia rozhodli, že mu každý rok dajú len jeden darček z jeho zoznamu. Aby to ale malého Merlina nezarmútilo, spravili to nasledovne. Každý rok mu dajú darček, ktorý ho poteší ostro viac, ako ten minulý rok! Pomôžte Merlinovim rodičom zistiť, koľko rokov im takto vystačí Merlinov zoznam?

Úloha

Na vstupe dostanete zoznam čísel \(a\), ktorý má dĺžku \(n\). Tento zoznam potom za seba \(n\)-krát skopírujeme. Podpostupnosť tohoto zoznamu dokážeme získať tak, že niektoré prvky vymažeme a ostatné necháme tak. Vašou úlohou je zistiť dĺžku najdlhšej rastúcej podpostupnosti takto vzniknutej postupnosti. Pre rastúcu postupnosť platí, že pre každé \(i\), \(a[i-1] < a[i]\).

Formát vstupu

Na prvom riadku dostanete číslo \(n\) \((1 \leq n \leq 10^5)\), počet Merlinových želaných darčekov. Na druhom riadku sa nachádza \(n\) čísel. Číslo \(a_i\) \((1 \leq a_i \leq 10^9)\) určuje, ako veľmi sa Merlinovi daný darček páči.

Formát výstupu

Na výstup vypíšte jedno číslo, dĺžku najdlhšej stúpajúcej podpostupnosti, ktorú dostaneme tak, že zopakujeme pôvodný Merlinov zoznam \(n\)-krát.

Hodnotenie

Existuje 5 sád vstupov, pre ktoré platia nasledovné obmedzenia:

Príklad

Input:

3
3 1 2

Output:

3

Z prvej kópie zoberieme \(1\) a \(2\) a z druhej zoberieme \(3\).

Input:

6
3 1 4 1 5 9

Output:

5

Výsledná postupnosť bude \(1, 3, 4, 5, 9\).