B - Reversi 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 700 点

問題文

N 個の石が一列に並んでいて、左から i 個目の石は色 C_i で塗られています。

すぬけ君は、以下の操作を 0 回以上の任意の回数行います。

  • 同じ色で塗られている 2 つの石を選ぶ。それらの石の間に置かれている石をすべて、選んだ石と同じ色で塗りかえる。

最終的な石の色の列としてありうるものの個数を 10^9+7 で割ったあまりを求めてください。

制約

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq C_i \leq 2\times 10^5(1\leq i\leq N)
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

N
C_1
:
C_N

出力

最終的な石の色の列としてありうるものの個数を 10^9+7 で割ったあまりを出力せよ。

入力例 1

5
1
2
1
2
2

出力例 1

3

以下の 3 通りの石の色の列を作ることができます。

  • 操作を行わないことで、(1,2,1,2,2)
  • 1,3 番目の石を選んで操作を行うことで、(1,1,1,2,2)
  • 2,4 番目の石を選んで操作を行うことで、(1,2,2,2,2)

入力例 2

6
4
2
5
4
2
4

出力例 2

5

入力例 3

7
1
3
1
2
3
3
2

出力例 3

5

Score : 700 points

Problem Statement

There are N stones arranged in a row. The i-th stone from the left is painted in the color C_i.

Snuke will perform the following operation zero or more times:

  • Choose two stones painted in the same color. Repaint all the stones between them, with the color of the chosen stones.

Find the number of possible final sequences of colors of the stones, modulo 10^9+7.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq C_i \leq 2\times 10^5(1\leq i\leq N)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
C_1
:
C_N

Output

Print the number of possible final sequences of colors of the stones, modulo 10^9+7.

Sample Input 1

5
1
2
1
2
2

Sample Output 1

3

We can make three sequences of colors of stones, as follows:

  • (1,2,1,2,2), by doing nothing.
  • (1,1,1,2,2), by choosing the first and third stones to perform the operation.
  • (1,2,2,2,2), by choosing the second and fourth stones to perform the operation.

Sample Input 2

6
4
2
5
4
2
4

Sample Output 2

5

Sample Input 3

7
1
3
1
2
3
3
2

Sample Output 3

5