D - Swap and Erase Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

数列 A = (A_1,\ldots,A_N) があります。これに対して、以下の 2 種類の操作を、任意の順番で任意の回数だけ行うことができます。

  • 操作直前の A の長さを K とする。1\leq i\leq K-1 を満たす整数 i を選び、A の第 i 項と第 (i+1) 項を入れ替える。
  • 操作直前の A の長さを K とする。1\leq i\leq K かつ A の第 1 項から第 i 項の値が全て等しいような整数 i を選び、A の第 1 項から第 i 項までを全て削除する。

A を空の数列にするために必要な合計操作回数の最小値を求めてください。

T 個のテストケースが与えられるので、それぞれについて解いてください。

制約

  • 1\leq T\leq 10^5
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq N
  • すべてのテストケースにわたる N の総和は 2\times 10^5 以下
  • 入力される値は全て整数

入力

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各ケースは以下の形式で与えられる。

N
A_1 A_2 \ldots A_N

出力

各テストケースに対する答えを順に改行区切りで出力せよ。

入力例 1

3
5
1 1 2 1 2
4
4 2 1 3
11
1 2 1 2 1 2 1 2 1 2 1

出力例 1

3
4
8

1 番目のテストケースについて、以下の 3 回の操作によって A を空の数列にすることができます。

  • A の第 3 項と第 4 項を入れ替える。結果として、A は (1,1,1,2,2) となる。
  • A の第 1 項から第 3 項までを削除する。結果として、A は (2,2) となる。
  • A の第 1 項から第 2 項までを削除する。結果として、A は空の数列となる。

2 番目のテストケースについて、A の第 1 項を削除する操作を 4 回行うことで A を空の数列にすることができます。また、3 回以下の操作では A を空の数列にすることはできません。

Score : 700 points

Problem Statement

There is a sequence A = (A_1,\ldots,A_N). You can perform the following two types of operations any number of times in any order:

  • Let K be the length of A just before the operation. Choose an integer i such that 1 \leq i \leq K-1, and swap the i-th and (i+1)-th elements of A.
  • Let K be the length of A just before the operation. Choose an integer i such that 1 \leq i \leq K and all the values from the 1-st through the i-th elements of A are equal, and delete all the elements from the 1-st through the i-th of A.

Find the minimum total number of operations required to make A an empty sequence.

You are given T test cases; solve each of them.

Constraints

  • 1\leq T\leq 10^5
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq N
  • The sum of N over all test cases is at most 2\times 10^5.
  • All input values are integers.

Input

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each case is given in the following format:

N
A_1 A_2 \ldots A_N

Output

Print the answer for each test case in order, separated by newlines.

Sample Input 1

3
5
1 1 2 1 2
4
4 2 1 3
11
1 2 1 2 1 2 1 2 1 2 1

Sample Output 1

3
4
8

For the 1st test case, A can be made empty by the following three operations:

  • Swap the 3rd and 4th elements of A. Now, A is (1,1,1,2,2).
  • Delete the 1st through 3rd elements of A. Now, A is (2,2).
  • Delete the 1st through 2nd elements of A. Now, A is an empty sequence.

For the 2nd test case, A can be made empty by deleting the 1st element four times. Also, it is impossible to make A empty in three or fewer operations.