小象有一个长度为 $n$ 的非负整数序列 $a_1$, $a_2$, $\ldots$, $a_n$。他想修改其中某一个元素 $a_x$ 的值，将其变成一个新的非负整数 $y$。他希望对于每一个 $a_x$ 都能找到最小的 $y$ 使得修改后整个序列的最长上升子序列长度最大化，你可以帮助他解决这个问题吗？
对于序列 $b_1$, $b_2$, $\ldots$, $b_n$，它的任何一个上升子序列可以用相应的下标序列 $p_1$, $p_2$, $\ldots$, $p_m$ 描述，其中 $m$ 是这个上升子序列的长度，而 $1 \leq p_1 < p_2 < \ldots < p_m \leq n$ 且 $b_{p_1} < b_{p_2} < \ldots < b_{p_m}$。
输入包含多组测试数据。输入的第一行包含一个正整数 $T$ ($1 \leq T \leq 1000$)，表示测试数据的组数。接下来依次描述每组测试数据，对于每组测试数据：
第一行包含一个正整数 $n$ ($1 \leq n \leq 10^5$)，含义如题面所示。
第二行包含 $n$ 个非负整数，表示 $a_1$, $a_2$, $\ldots$, $a_n$ ($0 \leq a_i \leq 10^9$)。
保证所有测试数据的 $n$ 之和不超过 $10^6$。
对于每组数据，输出 $n$ 行，其中第 $x$ 行包含两个整数，第一个整数表示修改 $a_x$ 能得到的最长上升子序列最大长度，第二个整数表示在实现最大长度的前提下最小的非负整数 $y$ 的值，这两个整数之间用恰好一个空格隔开，行末不要有多余的空格。
2 5 5 4 3 2 1 6 3 2 5 4 7 6
2 0 2 0 2 0 2 0 2 3 4 0 4 4 4 3 4 6 4 5 4 8
Comet OJ