当前没有测试数据。

Description

给定一个长度为 $n$ 的排列，求 $\text{Mex}_{i=l}^r a_i\times \text{mex}_{i=l}^r a_i$ 最大的一个区间 $(l,r)$。

定义 $\text{Mex}$ 是集合中 $[1,n]$ 中最后一个没有出现的数。$\text{mex}$ 是集合 $[1,n]$ 中第一个没有出现的数。

Format

Input

多组测试数组。

第一行一个正整数 $t$ 表示数据组数。

接下来 $t$ 组数据，每组两行，第一行一个正整数 $n$ 表示排列长度，第二行 $n$ 个正整数表示排列。

Output

输出共 $t$ 行，每行两个正整数 $(l,r)$ 表示答案区间。若有多组解，输出任意一组即可。

Samples

3
1
1
2
2 1
3
1 3 2

1 1
2 2
1 1

Note:

牛客小白月赛 E

2025 zstu 校赛 mid