D - Move One Card Left 解説 /

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

配点 : 400 点

問題文

正の整数からなる長さ N の列 A=(A _ 1,A _ 2,\ldots,A _ N) が与えられます。

列 A に対して次の操作をちょうど \mathbf{1} 回だけ行います。

  • A の要素を一つ選んで取り出し、残った列の元あった場所かそれより前に挿入する。より厳密には、以下の 2 つの操作を順に行う。
    • 1\le i\le N を満たす整数 i を一つ選び、長さ N-1 の列 X=(X _ 1,X _ 2,\ldots,X _ {N-1}) を (A _ 1,A _ 2,\ldots,A _ {i-1},A _ {i+1},A _ {i+2},\ldots,A _ N) とし、整数 Y を A _ i とする。
    • 1\le j\le i を満たす整数 j を一つ選び、長さ N の列 (X _ 1,X _ 2,\ldots,X _ {j-1},Y,X _ j,X _ {j+1},\ldots,X _ {N-1}) を新たな A とする。

要素を挿入するとき、列の左端や右端に挿入できる場合があることに注意してください。

操作の結果として得られる列が何通りあるか求めてください。

操作で選んだ (i,j) が異なる場合でも、列として等しい場合は同じものとして数えます。

制約

  • 1\le N\le2\times10 ^ 5
  • 1\le A _ i\le N\ (1\le i\le N)
  • 入力はすべて整数

入力

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

N
A _ 1 A _ 2 \ldots A _ N

出力

答えを出力せよ。

入力例 1

6
1 4 1 4 2 1

出力例 1

12

例えば、i=6,j=4 として操作を行うことで (1,4,1,1,4,2) を得ることができます。

他にも、以下の 11 通りの列を得ることができます。

  • (1,1,4,1,4,2)
  • (1,1,4,4,2,1)
  • (1,2,4,1,4,1)
  • (1,4,1,2,4,1)
  • (1,4,1,4,1,2)
  • (1,4,1,4,2,1)
  • (1,4,2,1,4,1)
  • (1,4,4,1,2,1)
  • (2,1,4,1,4,1)
  • (4,1,1,4,2,1)
  • (4,1,4,1,2,1)

よって、12 を出力してください。

入力例 2

5
1 1 1 1 1

出力例 2

1

異なる (i,j) によって得られる列でも、列として等しければ 1 つとして数えることに注意してください。

入力例 3

30
24 22 18 20 14 22 14 14 26 14 26 26 20 22 24 18 22 22 14 24 18 14 14 24 22 18 18 26 14 20

出力例 3

303

Score : 400 points

Problem Statement

You are given a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N consisting of positive integers.

The following operation is performed on the sequence A exactly once.

  • Choose one element of A, take it out, and insert it into the remaining sequence at its original position or earlier. More formally, perform the following two steps in order.
    • Choose an integer i satisfying 1\le i\le N, let the sequence X=(X _ 1,X _ 2,\ldots,X _ {N-1}) of length N-1 be (A _ 1,A _ 2,\ldots,A _ {i-1},A _ {i+1},A _ {i+2},\ldots,A _ N), and let the integer Y be A _ i.
    • Choose an integer j satisfying 1\le j\le i, and let the sequence (X _ 1,X _ 2,\ldots,X _ {j-1},Y,X _ j,X _ {j+1},\ldots,X _ {N-1}) of length N be the new A.

Note that in some cases the element can be inserted at the left end or the right end of the sequence.

Find the number of distinct sequences that can be obtained as a result of the operation.

Even if the pairs (i,j) chosen in the operation are different, the results are counted as the same if they are equal as sequences.

Constraints

  • 1\le N\le2\times10 ^ 5
  • 1\le A _ i\le N\ (1\le i\le N)
  • All input values are integers.

Input

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

N
A _ 1 A _ 2 \ldots A _ N

Output

Print the answer.

Sample Input 1

6
1 4 1 4 2 1

Sample Output 1

12

For example, performing the operation with i=6,j=4 yields (1,4,1,1,4,2).

Besides this, the following 11 sequences can be obtained.

  • (1,1,4,1,4,2)
  • (1,1,4,4,2,1)
  • (1,2,4,1,4,1)
  • (1,4,1,2,4,1)
  • (1,4,1,4,1,2)
  • (1,4,1,4,2,1)
  • (1,4,2,1,4,1)
  • (1,4,4,1,2,1)
  • (2,1,4,1,4,1)
  • (4,1,1,4,2,1)
  • (4,1,4,1,2,1)

Thus, print 12.

Sample Input 2

5
1 1 1 1 1

Sample Output 2

1

Note that sequences obtained by different pairs (i,j) are counted as one if they are equal as sequences.

Sample Input 3

30
24 22 18 20 14 22 14 14 26 14 26 26 20 22 24 18 22 22 14 24 18 14 14 24 22 18 18 26 14 20

Sample Output 3

303