h2. Restricţii

* $2 ≤ N ≤ 100 000$
* Considerând că şirul dat este $A = (a{~1~},a{~2~},...a{~N~})$, se numeşte subşir al lui $A$ un şir $B = (a{~i1~},a{~i2~},...a{~iK~})$ cu proprietatea că $1 ≤ i1 < i2 < ... < iK ≤ N$.

* $1 ≤ N ≤ 100 000$
* Considerând că şirul dat este $A = (a{~1~},a{~2~},...a{~N~})$, se numeşte subşir al lui $A$ un şir $B = (b{~i1~},b{~i2~},...b{~iN~})$ cu proprietatea că $1 ≤ i1 < i2 < ... < iK ≤ N$.

* Pe organizatori nu îi interesează dacă din subşir fac parte două sau mai multe persoane cu acelaşi loc preferat. Ei le dau biletele şi îi lasă pe ei să îşi rezolve problema.
h2. Exemplu

5449