A - Range Replace Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

長さ N の数列 A=(A_1,\ldots,A_N) が与えられます．あなたは以下の操作をちょうど一回行います．

  • 1\leq L \leq R \leq N なる整数組 (L,R) を選ぶ．A_L,A_{L+1},\ldots,A_R を全て A_L で置き換える．

操作後の A として考えられる数列は何通りですか．

制約

  • 入力される数値は全て整数
  • 1 \leq N \leq 10^6
  • 1\leq A_i \leq N

入力

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

N 
A_1 \ldots A_N

出力

答えを出力せよ．

入力例 1

4
1 1 2 3

出力例 1

4

操作後に考えられる数列は以下の 4 個です．

  • (1,1,1,1)
  • (1,1,1,3)
  • (1,1,2,2)
  • (1,1,2,3)

例えば，(1,1,1,3) は L=2,R=3 として操作を行うことで得られます．

入力例 2

10
2 5 6 5 2 1 7 9 7 2

出力例 2

41

Score : 400 points

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N. You perform the following operation exactly once.

  • Choose a pair of integers (L,R) such that 1\leq L \leq R \leq N. Replace each of A_L,A_{L+1},\ldots,A_R with A_L.

How many different sequences are possible as A after the operation?

Constraints

  • All input values are integers.
  • 1 \leq N \leq 10^6
  • 1\leq A_i \leq N

Input

The input is given from Standard Input in the following format:

N 
A_1 \ldots A_N

Output

Output the answer.

Sample Input 1

4
1 1 2 3

Sample Output 1

4

The possible sequences after the operation are the following four sequences:

  • (1,1,1,1)
  • (1,1,1,3)
  • (1,1,2,2)
  • (1,1,2,3)

For example, (1,1,1,3) can be obtained by performing the operation with L=2,R=3.

Sample Input 2

10
2 5 6 5 2 1 7 9 7 2

Sample Output 2

41