Temirulan vs. Pernekhan

Temirulan and Pernekhan have been given a sequence A consisting of n (1 ≤ n ≤ 5000) positive integers. They have decided to divide this sequence between them. Each of them must select a non-empty contiguous segment of the sequence, with Temirulan's segment coming before Pernekhan's. To ensure uniqueness, they want no integer to appear in both segments at the same time. Aidos, who is observing, is curious about the number of different ways they can achieve this division. Your task is to write a program that calculates the number of possible ways.

Input

The first line contains the integer n. The second line contains n integers A[i] (1 ≤ A[i] ≤ n, 1 ≤ i ≤ n), separated by spaces.

Output

Print a single integer representing the number of ways to split the sequence according to the rules.

Examples

Note

In the second test case, the sequence can be split in the following ways:

{ [1] [2] 3 2 }, { [1] [2 3] 2 }, { [1] [2 3 2] },

{ [1] 2 [3] 2 }, { [1] 2 [3 2] }, { [1] 2 3 [2] },

{ [1 2] [3] 2 }, { 1 [2] [3] 2 }, { 1 2 [3] [2] }