Given a sequence of positive integers $a_1, a_2, \ldots, a_n$, a triplet $(i, j, k)$ is called a "beautiful triplet" if it satisfies the following conditions:
- $1 \leq i < j < k \leq n$.
- Define the consecutive subsequence $a_i, a_{i+1}, \ldots, a_j$ as $A$ and the consecutive subsequence $a_j, a_{j+1}, \ldots, a_k$ as $B$. The subsequences $A$ and $B$ satisfy:
- Every value that appears in $A$ also appears in $B$.
- Every value that appears in $B$ also appears in $A$.
**Objective**: Given the sequence $a$, count the number of beautiful triplets $(i, j, k)$ in the sequence.
#### Input
- The first line contains an integer $n$ ($1 \leq n \leq 10^5$).
- The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^6$).
#### Output
- Output a single integer, which is the number of beautiful triplets in the given sequence.
#### Example
Input:
```
7
3 1 2 1 2 3 1
```
Output:
```
4
```
Explanation:
The valid beautiful triplets $(i, j, k)$ are:
1. $(1, 3, 5)$
2. $(1, 4, 6)$
3. $(2, 4, 6)$
4. $(3, 5, 7)$
#### Subtasks
- **Subtask 1 (20 poinGiven a sequence of positive integers $a_1, a_2, \ldots, a_n$, a triplet $(i, j, k)$ is called a "beautiful triplet" if it satisfies the following conditions:
- $1 \leq i < j < k \leq n$.
- Define the consecutive subsequence $a_i, a_{i+1}, \ldots, a_j$ as $A$ and the consecutive subsequence $a_j, a_{j+1}, \ldots, a_k$ as $B$. The subsequences $A$ and $B$ satisfy:
- Every value that appears in $A$ also appears in $B$.
- Every value that appears in $B$ also appears in $A$.
**Objective**: Given the sequence $a$, count the number of beautiful triplets $(i, j, k)$ in the sequence.
#### Input
- The first line contains an integer $n$ ($1 \leq n \leq 10^5$).
- The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^6$).
#### Output
- Output a single integer, which is the number of beautiful triplets in the given sequence.
#### Example
Input:
```
7
3 1 2 1 2 3 1
```
Output:
```
4
```
Explanation:
The valid beautiful triplets $(i, j, k)$ are:
1. $(1, 3, 5)$
2. $(1, 4, 6)$
3. $(2, 4, 6)$
4. $(3, 5, 7)$
#### Subtasks
- **Subtask 1 (20 points)**: $n \leq 100$.
- **Subtask 2 (20 points)**: $n \leq 1000$.
- **Subtask 3 (20 points)**: $n \leq 10^4$.
- **Subtask 4 (20 points)**: Each value appears exactly twice.
- **Subtask 5 (20 points)**: No additional constraints.
ts)**: $n \leq 100$.
- **Subtask 2 (20 points)**: $n \leq 1000$.
- **Subtask 3 (20 points)**: $n \leq 10^4$.
- **Subtask 4 (20 points)**: Each value appears exactly twice.
- **Subtask 5 (20 points)**: No additional constraints.
