NumberEater

Time limit1sMemory limit128 MB

Summary

Count the number of distinct value sets obtainable as the set of a contiguous subarray of the given sequence.

Level: Medium6 of 10
Topics: Hash map, Array, Two pointers
Solved: No attempts yet

Problem

NumberEater is a famous monster from Byteland. It eats numbers, but it is very picky: every day its meal must be unique. The monster is given a sequence of integers $a_1, a_2, \ldots, a_n$ . It chooses a start position $i$ and an end position $j$ ( $1 \le i \le j \le n$ ) and prepares a meal made of the elements $a_i, a_{i+1}, \ldots, a_j$ .

The monster considers two meals $[i_1, j_1]$ and $[i_2, j_2]$ to be identical when they contain the same set of numbers, that is:

$\{a_k : i_1 \le k \le j_1\} = \{a_k : i_2 \le k \le j_2\}$

Help NumberEater count how many different meals it can prepare using the sequence $a$ .

Input

The first line contains one integer $n$ ( $1 \le n \le 500$ ), the length of the sequence $a$ . Each of the next $n$ lines contains one element of the sequence. Every element is at least $1$ and at most $500$ .

Output

Print a single integer: the number of different meals that NumberEater can prepare.

Examples1

Example 1
Input
```
6
1
2
3
1
2
3
```
Expected output
```
7
```