問題文の条件を満たす \((a, b)\) が数列内においてどのように配置されているのかを考えましょう。すると、条件を満たすのは

\[\dots, a, b, \dots, a, b, \dots\]

あるいは

\[\dots, a, b, \dots, b, a, \dots\]

のような形に限られることがわかります。ここから、問題文の条件は、次の条件をすべて満たすことと等価であることがわかります。

• \(A\) 内において \(a\) 同士は隣接していない。
• \(A\) 内において \(b\) 同士は隣接していない。
• \(A\) 内の \(a\) の位置と \(b\) の位置をそれぞれ \(p_{a,1}, p_{a,2}\) および \(p_{b,1}, p_{b,2}\) とする。
  数列 \((p_{a,1}, p_{a,2}, p_{b,1}, p_{b,2})\) をソートしたものを \(v = (v_1, v_2, v_3, v_4)\) とする。
  この時、\(v_1 + 1 = v_2\) かつ \(v_3 + 1 = v_4\) が成り立っている。

また、条件を満たす \((a, b)\) は \(A\) 内において隣接している必要がある点もわかります。
よって、\(1 \leq i \leq 2N-1, A_i \neq A_{i+1}\) を満たすすべての \((A_i, A_{i+1})\) に対して上記の条件を満たすかどうかを確認すれば、条件を満たす \((a, b)\) を漏れなく数え上げることができます。 (同じ \((a, b)\) の組を複数回数えてはならない点に注意してください。) 条件の判定は \(1\) 回あたり \(\mathrm{O}(1)\) でできるので、この問題を \(\mathrm{O}(N)\) で解くことができて、これは十分高速です。

• 実装例(C++)

#include <algorithm>
#include <iostream>
#include <set>
#include <utility>
#include <vector>
using namespace std;

int main() {
  int T;
  cin >> T;
  while (T--) {
    int N;
    cin >> N;
    vector<int> A(2 * N);
    for (auto& a : A) cin >> a;

    vector<vector<int>> position(N + 1);
    for (int i = 0; i < 2 * N; i++) position[A[i]].push_back(i);

    set<pair<int, int>> answers;
    for (int i = 0; i + 1 < 2 * N; i++) {
      int a = A[i], b = A[i + 1];
      if (position[a][0] + 1 == position[a][1]) continue;
      if (position[b][0] + 1 == position[b][1]) continue;
      vector<int> v{position[a][0], position[a][1], position[b][0],
                    position[b][1]};
      sort(begin(v), end(v));
      if (v[0] + 1 == v[1] and v[2] + 1 == v[3]) {
        answers.emplace(minmax(a, b));
      }
    }
    cout << answers.size() << "\n";
  }
}