Considerăm un şir de N numere naturale distincte a₁, a₂, ..., a_N. Pentru fiecare termen a_i definim predecesorul său, dacă există, ca fiind cel mai din dreapta termen a_j, cu j < i şi a_j < a_i. De exemplu, pentru şirul 8, 12, 2, 4, 3, 10, 9, 7, 5, 6, numărul 8 este predecesorul lui 12, 3 este predecesorul lui 5, 10 nu este predecesorul niciunui număr, la fel 4 nu este predecesor pentru alt număr, 2 nu are predecesor.

Cerinţă

Scrieţi un program care determină câte numere din şir nu sunt predecesori ai niciunui alt număr.

Date de intrare

Fişierul de intrare predecesor.in conţine pe prima linie numărul natural N reprezentând numărul de termeni ai şirului. Pe următoarea linie se găsesc, separaţi prin câte un spaţiu, termenii a₁, a₂, ..., a_N ai şirului.

Date de ieşire

Fişierul de ieşire predecesor.out va conţine o singura linie pe care va fi scris un singur număr natural reprezentând numărul de termeni ai şirului care nu sunt predecesori ai niciunui alt număr.

Restricţii

• 3 <= N <= 500 000
• 1 <= a_i <= 1 000 000 000, pentru orice 1 <= i <= N

Exemplu

predecesor.in	predecesor.out
10 8 12 2 4 3 10 9 7 5 6	6

prof. Dan Pracsiu

Grupul Şcolar „Ştefan Procopiu” Vaslui

dpracsiu@yahoo.com