当前没有测试数据。

追忆

题目背景

若花胜去年红，坞中莲蕊竟已开已落，醉倒芳丛，一眼岁月都无穷。 — 东风志

年少时的时光，总是与许多独特的景象相伴：或许是那一缕东风，或许是那一片柳絮，又或许是那一抹剑光、一盏浊酒、一地月光。这些景象早已远去，化作一行行诗句。

题目描述

诗卷共有 $n$ 行，第 $i$ 行诗描述了第 $i$ 个景象 $a_i$，相同的景象可能出现在不同的行中。你要选取一个连续区间 $[l,r]$ 作为最深刻的忆境。

一段忆境的价值等于：区间 $[l,r]$ 内不同景象的种类数，加上区间外不同景象的种类数。

请你求出忆境价值的最大可能值。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

对于每组测试数据，第一行输入一个整数 $n$，表示序列长度；第二行输入 $n$ 个整数 $a_1,a_2,ldots,a_n$。

输出格式

对于每组测试数据，输出一行一个整数，表示忆境的最大价值。

2
4
1 2 2 1
4
1 2 1 2

4
4

数据范围与提示

• $1 \le T \le 10^6$
• $1 \le n \le 10^6$
• 所有测试数据的 $\sum n \le 10^6$
• $1 \le a_i \le n$

第一组数据选择区间 $[2,3]$ 时，区间内有景象 $2$，区间外有景象 $1$，价值为 $2$；选择整个区间时区间内有 $1,2$ 两种、区间外为空，价值为 $2$。但选择 $[1,2]$ 或 $[3,4]$ 时区间内、外各有 $1,2$ 两种，价值为 $4$。