Cerința

Generalul vostru preferat, Gaius Julius Caesar se află într-o nouă campanie militară. De data aceasta el deține N soldați numerotați de la 1 la N. Această armată este definită printr-un vector unidimensional legions, legions[i] înseamnand ca al i-lea soldat face parte din legiunea legions[i]. Julius Caesar vrea să ia cu el în luptă o secvență st.....dr de soldați. Deoarece nu vrea să existe discriminare, odată luat un soldat dintr-o legiune x, toți soldații din legiunea x trebuie sa fie prezenți în st....dr. De exemplu dacă legiunile soldaților sunt [1 , 2 , 1] atunci Julius Caesar nu poate lua secvența determinată de primul soldat, deoarece conține un soldat din legiunea 1, dar nu îi contine pe toți. Prin urmare secvențele bune ar fi: [1 , 3] și [2 ,2]. Julius Caesar se intreabă câte astfel de intervale de soldați există în armata sa.

Date de intrare

Fișierul de intrare caesar.in conține pe prima linie un număr N reprezentând numărul de soldați pe care îi deține Julius Caesar. Pe a doua linie se află N valori reprezentând legiunile soldaților.

Date de ieșire

Fișierul de ieșire caesar.out conține numărul de secvențe cu proprietatea dată.

Restricții și precizări

• N ≤ 100.000, legions[i] ≤ 1e9 oricare i din [1, N].
• Pentru 10 puncte, N ≤ 100, legions[i] ≤ 1e9 oricare i din [1, N].
• Pentru alte 10 puncte, N ≤ 1000, legions[i] ≤ 1e9, oricare i din [1, N].
• Pentru alte 10 puncte, N ≤ 100.000, legions[i] ≤ 100, oricare i din [1, N].
• Pentru restul de 70 puncte se respectă restricțiile inițiale.

Exemplu:

caesar.in

3
1 2 3

caesar.out

6

caesar.in

3
1 2 1 

caesar.out

2

Explicație

În primul exemplu , orice secvență este bună.
În al doilea exemplu , secvențele bune sunt [1 , 3] și [2 , 2].