3732 - Abundant Sequences

Created by Oreste Nillar Cambara
Added by Oreste (2016-09-07)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Given a sequence S of N numbers, a contiguous subsequence Si, Si+1, ..., Sj-1, Sj is called abundant if every number in the subsequence appears at least twice in the subsequence. An abundant contiguous subsequence is called maximal if it is not contained in a longer abundant contiguous subsequence. Count the number of maximal abundant contiguous subsequences of S.
Dada una secuencia S de N números, una subsecuencia continua Si, Si+1, ..., Sj-1, Sj es llamada abundante si cada número en la subsecuencia aparece al menos dos veces en ella. Una subsecuencia continua abundante es llamada maximal si no está contenida en una subsecuencia continua abundante mayor. Cuente el número de subsecuencias continuas abundantes que son maximales en S.
Given a sequence S of N numbers, a contiguous subsequence Si, Si+1, ..., Sj-1, Sj is called abundant if every number in the subsequence appears at least twice in the subsequence. An abundant contiguous subsequence is called maximal if it is not contained in a longer abundant contiguous subsequence. Count the number of maximal abundant contiguous subsequences of S.

Input specification

The first line of input contains an integer N (1 N 105) indicating the number of elements in S. The second line contains exactly N space-separated integer numbers Si (1 Si 105 for 1 N) representing the elements of the sequence S in that order.
La primera línea de entrada contiene un entero N (1 N 105) indicando el número de elementos en S. La segunda línea contiene exactamente N números enteros separados por un espacio Si (1 Si 105 para 1 N) representando los elementos de la secuencia S en ese orden.
The first line of input contains an integer N (1 N 105) indicating the number of elements in S. The second line contains exactly N space-separated integer numbers Si (1 Si 105 for 1 N) representing the elements of the sequence S in that order.

Output specification

In a single line, print the number of maximal abundant subsequences of S.
En una línea debe imprimir el número de subsecuencias continuas abundantes que son maximales en S.
The first line of input contains an integer N (1 N 105) indicating the number of elements in S. The second line contains exactly N space-separated integer numbers Si (1 Si 105 for 1 N) representing the elements of the sequence S in that order.

Sample input

13
4 1 2 3 2 3 4 2 2 5 3 3 5

Sample output

2

Hint(s)

In this sample test case, there are two contiguous subsequences which are maximal abundant: 2 3 2 3 and 2 2 5 3 3 5.
En el ejemplo de entrada, hay dos subsecuencias abundantes que son maximales en S: 2 3 2 3 y 2 2 5 3 3 5.
In this sample test case, there are two contiguous subsequences which are maximal abundant: 2 3 2 3 and 2 2 5 3 3 5.