Color Deletion

Given a sequence of positive integers \(A_1, A_2, \dots, A_n\) where each integer represents a color, you are allowed to remove a color by deleting all positions \(j\) with \(A_j\) equal to that color. After deleting some colors (possibly none), the remaining sequence (with the original order preserved) might be split into several segments. A removal scheme is considered valid if the remaining sequence is non-empty and forms one contiguous block of the original sequence.

More formally, a removal scheme corresponds to a subset \(S\) of colors to remove. Let the set of indices of retained numbers be \(I = \{ j \mid A_j \notin S \}\). The scheme is valid if \(I\) is non-empty and if \(L = \min I\) and \(R = \max I\) then \(I = \{L, L+1, \dots, R\}\).

This is equivalent to the existence of an interval \([L,R]\) (with \(1 \le L \le R \le n\)) such that every color \(c\) that appears in \([L,R]\) satisfies

[ L \le L(c) \quad\text{and}\quad R(c) \le R ]

where \(L(c)\) and \(R(c)\) denote the first and last occurrence of color \(c\) in the sequence. Two removal schemes are considered different if there exists at least one color which is removed in one scheme but not in the other.

Your task is to count the number of valid removal schemes.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) \( (1 \le n)\).
• The second line contains \(n\) positive integers \(A_1, A_2, \dots, A_n\) separated by spaces.

outputFormat

Output a single integer -- the number of valid removal schemes.

sample

5
1 2 3 4 5

15