Variable Subsequences

We are looking for variable subsequences of a given sequence $a = (a_1, a_2, \dots, a_n)$. A subsequence is obtained by removing any number of terms (possibly none). Formally, a subsequence of $a$ is any sequence $(a_{i_1}, a_{i_2}, \dots, a_{i_k})$ with $1 \le i_1 < i_2 < \dots < i_k \le n$.

A variable subsequence is a subsequence in which every two consecutive terms are different. For example, $(1, 3, 1, 2)$ is a variable subsequence of $(1, 2, 3, 1, 3, 2, 2)$.

We want to count how many distinct, nonempty variable subsequences the sequence has. Two subsequences are distinct if their sets of positions in $a$ are different. For instance, $(1, 2, 3, 1, 3, 2, 2)$ contains two distinct variable subsequences of the form $(1, 3, 1, 2)$.

The first line contains one integer $n$ ($2 \le n \le 500{,}000$), the length of the sequence $a$. The second line contains $n$ integers $a_i$ ($1 \le a_i \le 500{,}000$) separated by spaces.

Print a single integer on one line: the number of nonempty variable subsequences of the input sequence modulo $10^9 + 7$.

For the sequence $(1, 2, 1, 1)$, the counted variable subsequences are:

• $(1)$: counted three times (positions 1, 3, and 4)
• $(2)$: counted once
• $(1, 2)$: counted once
• $(2, 1)$: counted twice
• $(1, 2, 1)$: counted twice

In total there are $3 + 1 + 1 + 2 + 2 = 9$ of them.