Voltas sem Repetição
Uma transportadora registra o código de cada depósito visitado, na ordem em que o caminhão passou por eles. Um trecho de viagem é uma volta limpa se começa e termina em depósitos com o mesmo código e, antes do retorno final, não visita nenhum código duas vezes.
Formalmente, um par de índices l < r é válido quando a[l] = a[r] e os valores a[l], a[l+1], ..., a[r-1] são todos distintos. Observe que o depósito final não participa dessa exigência de distinção: justamente por ser o retorno, seu código se repete.
Determine quantas voltas limpas existem. Trechos com índices diferentes são contados separadamente.
Input
A primeira linha contém um inteiro n. A segunda contém n inteiros a1, ..., an, os códigos dos depósitos.
Restrições:
1 ≤ n ≤ 200000; 1 ≤ ai ≤ 10^9. A resposta cabe em inteiro de 64 bits.
Output
Imprima um inteiro: a quantidade de voltas limpas.
Samples
Sample 1
Input
7 1 2 3 1 2 2 1
Output
3
Entre as voltas válidas estão as que terminam no primeiro retorno ao depósito 1 e a volta imediata entre os dois depósitos de código 2. Voltas que repetem um código antes do último depósito são inválidas.