AT_abc399_d [ABC399D] Switch Seats

> $ N $ 組のカップルが一列に座っています。 > $ 2 $ 組のカップルであって、もともと両方のカップルは隣り合わせで座っておらず、かつ $ 4 $ 人の間で席を交換することで両方のカップルが隣り合わせで座れるようになる組の個数を数えてください。 長さ $ 2N $ の数列 $ A=(A_1,A_2,\dots,A_{2N}) $ があります。 $ A $ には $ 1, 2, \dots, N $ がそれぞれ $ 2 $ 回ずつ登場します。 $ 1 \leq a \lt b \leq N $ を満たす整数対 $ (a, b) $ であって以下の条件を全て満たすものの個数を求めてください。 - $ A $ 内において $ a $ 同士は隣接していない。 - $ A $ 内において $ b $ 同士は隣接していない。 - 次の操作を $ 1 $ 回以上自由な回数行うことで、 $ A $ 内において $ a $ 同士が隣接していて、かつ $ b $ 同士が隣接している状態にすることができる。 - $ A_i = a, A_j = b $ を満たす整数対 $ (i, j) $ $ (1 \leq i \leq 2N, 1 \leq j \leq 2N) $ を選び、 $ A_i $ と $ A_j $ を入れ替える。 $ T $ 個のテストケースが与えられるので、それぞれに対して答えを求めてください。

入力は以下の形式で標準入力から与えられる。ここで、 $ \mathrm{case}_i $ は $ i $ 番目のテストケースを意味する。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_{2N} $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースの答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて考えます。 $ (a, b)=(1, 2) $ は問題文の条件を満たします。理由は次の通りです。 - $ A $ 内において $ 1 $ 同士は隣接していない。 - $ A $ 内において $ 2 $ 同士は隣接していない。 - $ (i,j)=(1, 6) $ として $ A_1 $ と $ A_6 $ を入れ替える操作を行うことで、 $ 1 $ 同士が隣接していて、かつ $ 2 $ 同士が隣接している状態にすることができる。 問題文の条件を満たす $ (a, b) $ は $ (1, 2) $ のみです。 ### Constraints - $ 1 \leq T \leq 2 \times 10^5 $ - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq A_i \leq N $ - $ A $ には $ 1, 2, \dots, N $ がそれぞれ $ 2 $ 回ずつ登場する - 全てのテストケースに対する $ N $ の総和は $ 2 \times 10^5 $ 以下 - 入力される値は全て整数