CF1905F Field Should Not Be Empty

给定一个长度为 $n$ 的排列 $p$。 我们称下标 $x$ 是好的，如果对于所有 $y < x$ 都有 $p_y < p_x$，并且对于所有 $y > x$ 都有 $p_y > p_x$。我们用 $f(p)$ 表示排列 $p$ 中好的下标的数量。 你可以进行如下操作：选择两个不同的下标 $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)$ 的最大值。

在第一个测试用例中，$p = [1,2,3,4,5]$，$f(p)=5$，已经是最大值。但必须进行一次操作。可以选择 $i=1$ 和 $j=2$，使 $p = [2,1,3,4,5]$，此时 $f(p)=3$。 在第二个测试用例中，可以选择 $i=1$ 和 $j=2$，将 $p$ 变为 $[1,2,3,4,5]$，此时 $f(p)=5$。 由 ChatGPT 4.1 翻译