题目描述

睿爸不会玩吃鸡或者打王者，只会玩玩开心消消乐，最近呀，他玩了一个非常特别的消消乐，这个消消乐的规则跟一般的消消乐不太一样。

这个消消乐中共有 $n$ 个方块排列成一排，每个方块均有一个标号，分别为 $a_1,a_2,a_3,\cdots,a_n$。

游戏一开始需要设置其中一种方块为 消除块，它们是不可以被消除的，而当选择了消除块后，游戏会自动在这 $n$ 个方块序列的前后各添加一个消除块。

而睿爸可以进行的操作就是，选择两个消除块，这两个块之间的所有方块将被删除。

但是注意，若选择的两个消除块之间存在消除块，则此次消除将会失败。

当所有非消除块被消除完后，游戏结束，而每一次操作会降低 $1$ 分得分，即操作次数越少，得分越高。

例如有 $5$ 个方块 $\{1,2,3,2,1\}$，睿爸 可以选择的游戏流程如下：

1. 选择 $3$ 为消除块，游戏自动在首尾各添加一个消除块，方块序列变为 $\{3,1,2,3,2,1,3\}$；

2. 选择 $a_0$ 和 $a_3$ 两个消除块进行消除，方块序列变为 $\{3,3,2,1,3\}$；

3. 继续选择 $a_1$ 和 $a_4$ 两个消除块进行消除，方块序列变为 $\{3,3,3\}$，游戏结束。 在这个游戏过程中，睿爸 总共进行了 $2$ 次操作，但是显然有操作次数更少的方法：

4. 选择 $1$ 为消除块，游戏自动在首尾各添加一个消除块，方块序列变为 $\{1,1,2,3,2,1,1\}$。

5. 选择 $a_1$ 和 $a_5$ 两个消除块进行消除，方块序列变为 $\{1,1,1,1\}$，游戏结束。 这样 睿爸 只需要 $1$ 次操作即可。

现在睿爸为了偷懒，他想知道每一轮游戏中，选择哪种消除块可以使得操作次数最少。

输入格式

第一行包含一个正整数 $T$ 表示共有多少轮游戏。

对于每轮游戏输入包含两行：

1. 第一行包含一个正整数 $n$ 表示这轮共有多少个方块。
2. 第二行包含 $n$ 个整数 $a_1,a_2,a_3,\cdots,a_n$ 分别表示每个方块的编号。

输出格式

对于每一轮游戏输出包含两个整数，分别表示选择的消除块的编号和最少需要的操作次数。

若存在多种消除块方案可以使得操作次数最少，那么选择最小的消除块编号。

样例

3
4
2 2 2 2
5
1 2 3 4 5
11
2 1 2 3 2 1 2 3 1 2 2

2 0
1 1
3 3

数据范围

对于 $30\%$ 的数据，$T \leq 10, 2 \leq n \leq 10^2$。

对于 $100\%$ 的数据，$T \leq 1000, 2 \leq n \leq 10^5 , 1 \leq a_i \leq n ,\sum{n} \leq 2 * 10^5$。