CF1335E2 Three Blocks Palindrome (hard version)

本题的简单版和困难版的唯一区别在于约束条件不同。 给定一个由 $n$ 个正整数组成的序列 $a$。 我们定义“三段回文串”为满足以下条件的序列：该序列至多只包含两种不同的元素（设为 $a$ 和 $b$，其中 $a$ 可以等于 $b$），且形式如下：$[\underbrace{a, a, \dots, a}_{x}, \underbrace{b, b, \dots, b}_{y}, \underbrace{a, a, \dots, a}_{x}]$。其中 $x, y$ 是大于等于 $0$ 的整数。例如，序列 $[]$、$[2]$、$[1, 1]$、$[1, 2, 1]$、$[1, 2, 2, 1]$ 和 $[1, 1, 2, 1, 1]$ 都是三段回文串，而 $[1, 2, 3, 2, 1]$、$[1, 2, 1, 2, 1]$ 和 $[1, 2]$ 不是。 你的任务是从 $a$ 中选择一个最长的子序列，使其为三段回文串。 你需要回答 $t$ 组独立的测试用例。 回顾一下，如果序列 $t$ 是序列 $s$ 的子序列，则 $t$ 可以通过从 $s$ 中删除零个或多个元素且不改变剩余元素的顺序得到。例如，如果 $s=[1, 2, 1, 3, 1, 2, 1]$，那么可能的子序列有：$[1, 1, 1, 1]$、$[3]$ 和 $[1, 2, 1, 3, 1, 2, 1]$，但 $[3, 2, 3]$ 和 $[1, 1, 1, 1, 2]$ 不是。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是 $t$ 组测试用例。 每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示 $a$ 的长度。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 200$），其中 $a_i$ 是 $a$ 的第 $i$ 个元素。注意 $a_i$ 的最大值为 $200$。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$（$\sum n \le 2 \times 10^5$）。

对于每组测试用例，输出一个整数，表示 $a$ 的某个三段回文子序列的最大可能长度。

由 ChatGPT 4.1 翻译