8311번 - Variable Subsequences 다국어

문제

We are looking for variable subsequences of a given sequence a = (a₁, a₂, ..., a_n). A subsequence is obtained from a sequence by removing any number of its terms (possibly 0). More formally, a subsequence of the sequence a is any sequence (a_i1, a_i2, ..., a_ik), for which 1 ≤ i₁ < i₂ < ... < i_k ≤ n A variable subsequence is a subsequence such that every two its consecutive terms are different. For example, the sequence (1, 3, 1, 2) is a variable subsequence of the sequence (1, 2, 3, 1, 3, 2, 2).

We would like to know how many distinct and nonempty variable subsequences of a given sequence are there. Two subsequences are considered distinct if the sets of positions in a corresponding to them are different. For instance, the sequence (1, 2, 3, 1, 3, 2, 2) contains two distinct variable subsequences of the form (1, 3, 1, 2).

입력

The first line of the standard input contains one integer n (2 ≤ n ≤ 500,000), denoting the length of the sequence a. The second line contains n integers a_i (1 ≤ a_i ≤ 500,000).

출력

Your program should write to the first and only line of the standard output a single integer: the number of nonempty variable subsequences of the input sequence modulo 10⁹ + 7.

제한

힌트

The considered subsequences of the sequence (1, 2, 1, 1) are:

• (1) - counted three times,
• (2) - counted once,
• (1, 2) - counted once,
• (2, 1) - counted twice and
• (1, 2, 1) - counted twice.