P4065 [JXOI2017] Colors

Kelian has a sequence of positive integers of length $n$, denoted by $A_i$, where equal integers represent the same color. Kelian thinks the sequence is too long, so she decides to choose some colors and delete all positions of those colors. Deleting color $i$ is defined as removing from the sequence all positions $j$ such that $A_j = i$. However, sometimes after deletions, the entire sequence breaks into several segments. Kelian does not like that, so she wants to know how many ways to delete colors will make the remaining sequence non-empty and contiguous. For example, for the color sequence $\{1, 2, 3, 4, 5\}$, after deleting color $3$, the sequence becomes two segments $\{1, 2\}$ and $\{4, 5\}$, which does not satisfy the requirement. After deleting color $1$, the sequence becomes $\{2, 3, 4, 5\}$, which satisfies the requirement. Two schemes are different if and only if there exists at least one color $i$ that is deleted in exactly one of them.

The first line contains an integer $T$, the number of test cases. For each test case, the first line contains an integer $n$, the length of the sequence; the second line contains $n$ integers describing the color sequence.

For each test case, output a single integer denoting the answer.

The valid deletion schemes are $\{1\}, \{1, 3\}, \{1, 2, 3\}, \{1, 3, 4\}, \{2, 3, 4\}, \varnothing$. For $20\%$ of the testdata, it is guaranteed that $1 \le \sum n \le 20$. For $40\%$ of the testdata, it is guaranteed that $1 \le \sum n \le 500$. For $60\%$ of the testdata, it is guaranteed that $1 \le \sum n \le 10^4$. For $100\%$ of the testdata, it is guaranteed that $1 \le T, \sum n \le 3 \times 10^5, 1 \le A_i \le n$. $\text{Statement fixed by @Starrykiller.}$ Translated by ChatGPT 5