给定一个长度为 $$$n$$$ 的排列 $$$p$$$(长度为 $$$n$$$ 的排列是一个长度为 $$$n$$$ 的数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个整数只出现一次)。
您可以执行以下操作任意次数(可能为零):
1.选择两个不同的元素$$$x$$$和$$$y$$$并将它们从排列中删除;
2. 将 $$$x$$$ 和 $$$y$$$ 中的最小值插入排列中,使其成为第一个元素;
3. 将 $$$x$$$ 和 $$$y$$$ 中的最大值插入排列中,使其成为最后一个元素。
例如,如果$$$p = [1, 5, 4, 2, 3]$$$,并且我们想要对元素$$$3$$$和$$$5$$$进行运算,那么在第一步运算之后,排列变为$$$p = [1, 4, 2]$$$;当我们插入元素后,它就变成了$$$p = [3, 1, 4, 2, 5]$$$。
您的任务是计算上述最少操作数,以升序对排列 $$$p$$$ 进行排序(即变换 $$$p$$$ 使得 $$$p_1 < p_2 < \dots < p_n$$$)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 排列中的元素数量。
测试用例的第二行包含从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数 - 给定的排列 $$$p$$$。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 如上所述对数组 $$$p$$$ 按升序排序的最少操作数。
示例
输入 #1
4 5 1 5 4 2 3 3 1 2 3 4 2 1 4 3 6 5 2 4 1 6 3
输出 #1
2 0 1 3
注意
在第一个示例中,您可以按如下方式进行操作:
1. 在排列$$$p = [1, 5, 4, 2, 3]$$$中,我们选择元素$$$4$$$和$$$2$$$,那么,应用运算后,排列变为$$$p = [2, 1, 5, 3, 4]$$$;
2. 在排列$$$p = [2, 1, 5, 3, 4]$$$中,我们选择元素$$$1$$$和$$$5$$$,那么,应用运算后,排列变为$$$p = [1, 2, 3, 4, 5]$$$。