该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

$\hspace{15pt}$这道题是 B 题的共轭题目！

$\hspace{15pt}$给你一个长度为 $N$ 的排列 $P = (P_1, P_2, \dots ,P_N)$ ，该排列由 $(1, 2, 3, \dots, N)$ 组成.

$\hspace{15pt}$对于一个长度为 $N$ 排列 $Q$ 来说，定义 $Q$ 的姊妹排列 $\bar{Q}$ 是执行下面操作刚好一次之后能产生的新排列中 字典序 最小的排列.

• 选择一个二元组 $(l, r)$ 满足 $1\leq l \leq r \leq N$ ，然后翻转 $(Q_l, Q_{l + 1}, \dots ,Q_{r-1},Q_{r})$, 换句话说，把排列 $Q = (Q_1, Q_2, \dots ,Q_N)$ 替换成 $\bar{Q} = (Q_1,\dots, Q_{l-1},Q_r, Q_{r-1}, \dots , Q_{l+1}, Q_{l},Q_{r+1}, \dots,Q_N)$

$\hspace{15pt}$对于 $P$ 来说，可能存在多个二元组 $(l, r)$，使得操作后都有 $\bar{P}$，你要输出 字典序 最小的二元组.

$\hspace{15pt}$形式化的讲，当两个二元组 $l$ 不同时，$l$ 更小的字典序小，相同时，$r$ 更小的字典序小.

$\hspace{15pt}$给你 $T$ 组样例，请你分别求解每一个.

注意本题时空限制

Constraints

• $1 \leq T$
• $1 \leq N \leq 1.5 \times 10^7$
• $P$ 是 $(1, 2, \dots, N)$ 的排列
• $N$ 的和不超过 $1.5 \times 10^7$
• 所有输入均为整数

Input

$\hspace{15pt}$通过标准输入输入数据，满足以下格式：

$T \\ case_1 \\ case_2\\ .\\ .\\ case_T\\$

$\hspace{15pt}$每一组测试用例满足以下格式：

$N \\ P_1 \ P_2 \ P_3 \ \dots \ P_N$

Output

$\hspace{15pt}$输出共 $T$ 行，对于第 $i$ 行，你要输出第 $i$ 组测试用例的答案.

$\hspace{15pt}$对于每一个测试用例，你要输出 $2$ 个数字，表示答案二元组 $(l_i, r_i)$.

Samples

2
3
1 3 2
1
1

2 3
1 1