思路

我们可以使用 最大堆（或最小堆），来实时维护当前学习过程中最久未遗忘的汉字的记忆值。这样做的好处是：

1. 每次学习汉字之前，我们可以通过堆来快速地找出哪些汉字已经遗忘（即记忆值为 0）。
2. 使用优先队列可以避免在每次学习之前遍历所有汉字来衰减记忆值，提升效率。

算法步骤

题目内容

wida 小朋友快到上学的年纪了，为了帮助他进行识字学习，Tk 设计了一套学习计划。

我们用整数 $a_i$ 表示汉字类别，相同的数字表示同一个汉字。

学习计划为一个长度为 $n$ 的数组 {$a_1,a_2,...,a_n$}，Tk 将按照数组顺序依次教给 wida 小朋友。由于 wida 会边学边回看先前学过的汉字记忆，过程具体如下：

• 当某个汉字 $a_i$ 是第 $x$ 次学习这个汉字，且之前未学过或已遗忘，该次学习令其获得 $x^2$ 点学习记忆；

• 当某个汉字 $a_i$ 是第 $x$ 次学习这个汉字，且之前尚未遗忘，该次学习在原有学习记忆上再增加 $x^2$ 点；

在学习每个汉字之前，所有未遗忘汉字的学习记忆均会衰减 $1$ 点；当某个汉字的学习记忆降为 $0$ 时，即视为遗忘(具体可以移步到样例解释)。

请计算 wida 小朋友在整个学习过程中，任意一时刻最多同时掌握(即未遗忘的)不同汉字的数量。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^4)$ 代表数据组数；

除此之外，保证单个测试文件中所有 $n$ 之和不超过 $2×10^5$ 。

每组测试数据描述如下：

• 第一行输入一个整数 $n(1 ≦n ≦ 2×10^5)$ ，表示学习计划的长度；

• 第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1 ≦ a_i ≦ n)$ ，表示学习计划中第 $i$ 次学习的汉字编号。

输出描述

对于每一组测试数据，新起一行，输出一个整数，代表 wida 小朋友在所有时刻最多掌握的不同汉字数量。

样例1

输入

2
3
1 2 3
6
1 1 2 2 3 4

输出

1
3

说明

在第一个样例中，$n=3$ 且序列为 {$1,2,3$}，每个汉字仅出现一次，学习后会在下一次学习前遗忘，因此最多同时掌握 $1$ 个汉字。

在第二个样例中，题目将具体解释此样例，对于每一次学习之前以及学习之后数字为 $1$ ~ $4$ 的每个学习记忆。

• 第一个汉字学习前：{$0,0,0,0$} ，第一个汉字学习后学习后：{$1,0,0,0$}

• 第二个汉字学习前：{$0,0,0,0$} ，第二个汉字学习后学习后：{$4,0,0,0$}

• 第三个汉字学习前：{$3,0,0,0$} ，第三个汉字学习后学习后：{$3,1,0,0$}

• 第四个汉字学习前：{$2,0,0,0$} ，第四个汉字学习后学习后：{$2,4,0,0$}

• 第五个汉字学习前：{$1,3,0,0$} ，第五个汉字学习后学习后：{$1,3,1,0$}

• 第六个汉字学习前：{$0,2,0,0$} ，第六个汉字学习后学习后：{$0,2,0,1$}

即学完第五个汉字后 wida 小朋友同时掌握的汉字最多，$3$ 个。