Field Should Not Be Empty
Contest: Codeforces Round 915 (Div. 2)
Difficulty rating: 2600
Tags: brute force, data structures, divide and conquer

You are given a permutation$$$^{\dagger}$$$ $$$p$$$ of length $$$n$$$.

We call index $$$x$$$ good if for all $$$y < x$$$ it holds that $$$p_y < p_x$$$ and for all $$$y > x$$$ it holds that $$$p_y > p_x$$$. We call $$$f(p)$$$ the number of good indices in $$$p$$$.

You can perform the following operation: pick $$$2$$$ distinct indices $$$i$$$ and $$$j$$$ and swap elements $$$p_i$$$ and $$$p_j$$$.

Find the maximum value of $$$f(p)$$$ after applying the aforementioned operation exactly once.

$$$^{\dagger}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input format:
Each test consists of multiple test cases. The first line of contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the permutation $$$p$$$.

The second line of each test case contain $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the elements of the permutation $$$p$$$.

It is guaranteed that sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the maximum value of $$$f(p)$$$ after performing the operation exactly once.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$p = [1,2,3,4,5]$$$ and $$$f(p)=5$$$ which is already maximum possible. But must perform the operation anyway. We can get $$$f(p)=3$$$ by choosing $$$i=1$$$ and $$$j=2$$$ which makes $$$p = [2,1,3,4,5]$$$.

In the second test case, we can transform $$$p$$$ into $$$[1,2,3,4,5]$$$ by choosing $$$i=1$$$ and $$$j=2$$$. Thus $$$f(p)=5$$$.

Example input:
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

Example output:
3
5
2
3
2

Editorial:
The key observation to this problem is that most swaps are useless. In fact, we can find that only $$$2n$$$ swaps can increase our initial cost:
• The first type of meaningful swaps is $$$(i,p_i)$$$
• For each $$$1 < i < n$$$, consider $$$k$$$ and $$$l$$$ such that $$$p_k = max(p_1,p_2,...,p_{i-1})$$$ and $$$p_l = min(p_{i+1},p_{i+2},...,p_n)$$$. The second type is $$$(k,l)$$$.
The reason why this is true is because the first type of swap can create a new good index ( since every good index must be a fixed point ) and the second type of swap can fix an already good index. It's obvious that if a swap does neither of the above, it can't increase our current cost.
Calculating $$$f(p)$$$ after each swap can be done with a segment tree. Consider adding one on the ranges $$$(min(i,p_i),max(i,p_i))$$$. Now an index is good if and only if its value is $$$1$$$, which is also the minimum value an index can have. Thus our segment tree has to find the number of minimums while performing range additions which can be easily maintained by lazy propagation.
This solution works in $$$O(nlog(n))$$$ time complexity.