가변 부분수열

수열 $a = (a_1, a_2, \dots, a_n)$ 이 주어진다. 수열의 부분수열은 원래 수열에서 임의 개수(0개일 수도 있다)의 항을 제거해 얻는 수열이다. 즉 $1 \le i_1 < i_2 < \dots < i_k \le n$ 을 만족하는 첨자들에 대해 $(a_{i_1}, a_{i_2}, \dots, a_{i_k})$ 형태로 쓸 수 있는 수열을 뜻한다.

가변 부분수열은 인접한 두 항이 항상 서로 다른 부분수열이다. 예를 들어 $(1, 3, 1, 2)$ 는 $(1, 2, 3, 1, 3, 2, 2)$ 의 가변 부분수열이다.

주어진 수열에서 공집합이 아니면서 서로 다른 가변 부분수열이 몇 개인지 구하자. 두 부분수열은 대응하는 위치(첨자) 집합이 서로 다르면 다른 것으로 센다. 예컨대 $(1, 2, 3, 1, 3, 2, 2)$ 에는 $(1, 3, 1, 2)$ 형태의 가변 부분수열이 서로 다른 두 가지 존재한다.

첫째 줄에 수열 $a$ 의 길이 $n$ ($2 \le n \le 500{,}000$) 이 주어진다. 둘째 줄에 $n$ 개의 정수 $a_i$ ($1 \le a_i \le 500{,}000$) 가 공백으로 구분되어 주어진다.

공집합이 아닌 가변 부분수열의 개수를 $10^9 + 7$ 로 나눈 나머지를 첫째 줄에 출력한다.

수열 $(1, 2, 1, 1)$ 에서 세는 가변 부분수열은 다음과 같다.

• $(1)$: 세 번 (1번, 3번, 4번 위치)
• $(2)$: 한 번
• $(1, 2)$: 한 번
• $(2, 1)$: 두 번
• $(1, 2, 1)$: 두 번

따라서 모두 $3 + 1 + 1 + 2 + 2 = 9$ 가지이다.