← 返回题目列表

Codeforces · 1905/F

F. 字段不应为空

中文机器翻译题面 查看原题

给你一个长度为 $$$n$$$ 的排列$$$^{\dagger}$$$ $$$p$$$。

如果对于所有 $$$y < x$$$ 都认为 $$$p_y < p_x$$$ 且对于所有 $$$y > x$$$ 都认为 $$$p_y > p_x$$$,我们称索引 $$$x$$$ 好。我们称 $$$f(p)$$$ 为 $$$p$$$ 中良好索引的数量。

您可以执行以下操作:选取 $$$2$$$ 不同索引 $$$i$$$ 和 $$$j$$$ 并交换元素 $$$p_i$$$ 和 $$$p_j$$$。

在应用上述操作一次后,找到 $$$f(p)$$$ 的最大值。

$$$^{\dagger}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 排列 $$$p$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 不同的整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — 排列 $$$p$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 执行一次操作后 $$$f(p)$$$ 的最大值。

示例

输入 #1

5
5
1 2 3 4 5
5
2 1 3 4 5
7
2 1 5 3 7 6 4
6
2 3 5 4 1 6
7
7 6 5 4 3 2 1

输出 #1

3
5
2
3
2

注意

在第一个测试用例中, $$$p = [1,2,3,4,5]$$$ 和 $$$f(p)=5$$$ 这已经是最大可能的。但无论如何都必须执行该操作。我们可以通过选择 $$$i=1$$$ 和 $$$j=2$$$ 得到 $$$f(p)=3$$$,这使得 $$$p = [2,1,3,4,5]$$$。

在第二个测试用例中,我们可以通过选择 $$$i=1$$$ 和 $$$j=2$$$ 将 $$$p$$$ 转换为 $$$[1,2,3,4,5]$$$。因此$$$f(p)=5$$$。