You are a knowledgeable assistant. Answer the following questions and think step by step. Please output the final answer within \boxed{}. This is an algorithmic problem, you need to return the optimal complexity of the best algorithm:
You are given a permutation $p$ of length $n$.

We call index $i$ good if for all $y < i$ it holds that $p_y < p_i$, and for all $y > i$ it holds that $p_y > p_i$. 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.

*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).*

Limit:
$n$ ($2 \leq n \leq 2 \cdot 10^5$)
$p_1, p_2, ..., p_n$ ($1 \leq p_i \leq n$)
user
This is an algorithmic problem, you need to return the optimal complexity of the best algorithm:
You are given a permutation $p$ of length $n$.

We call index $i$ good if for all $y < i$ it holds that $p_y < p_i$, and for all $y > i$ it holds that $p_y > p_i$. 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.

*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).*

Limit:
$n$ ($2 \leq n \leq 2 \cdot 10^5$)
$p_1, p_2, ..., p_n$ ($1 \leq p_i \leq n$)
O(n*log_2(n))
exactMatch
Computer Science/AI
This is an algorithmic problem, you need to return the optimal complexity of the best algorithm:
You are given a permutation $p$ of length $n$.

We call index $i$ good if for all $y < i$ it holds that $p_y < p_i$, and for all $y > i$ it holds that $p_y > p_i$. 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.

*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).*

Limit:
$n$ ($2 \leq n \leq 2 \cdot 10^5$)
$p_1, p_2, ..., p_n$ ($1 \leq p_i \leq n$)
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(n \log n)$ time complexity.

Code:
```c++
#include <bits/stdc++.h>
using namespace std;
struct aint
{
    vector<pair<int, int>> a;
    vector<int> lazy;
    void resize(int n)
    {
        a = vector<pair<int, int>>(4 * n);
        lazy = vector<int>(4 * n);
    }
    void init(int node, int left, int right)
    {
        a[node].second = (right - left + 1);
        if (left != right)
        {
            int mid = (left + right) / 2;
            init(2 * node, left, mid);
            init(2 * node + 1, mid + 1, right);
        }
    }
    void prop(int node, int left, int right)
    {
        a[node].first += lazy[node];
        if (left != right)
        {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
    pair<int, int> merge(pair<int, int> a, pair<int, int> b)
    {
        if (a.first == b.first)
        {
            return pair<int, int>{a.first, a.second + b.second};
        }
        return min(a, b);
    }
    void update(int node, int left, int right, int st, int dr, int val)
    {
        prop(node, left, right);
        if (right < st || left > dr)
        {
            return;
        }
        if (st <= left && dr >= right)
        {
            lazy[node] += val;
            prop(node, left, right);
            return;
        }
        int mid = (left + right) / 2;
        update(2 * node, left, mid, st, dr, val);
        update(2 * node + 1, mid + 1, right, st, dr, val);
        a[node] = merge(a[2 * node], a[2 * node + 1]);
    }
};
struct bit
{
    vector<int> a;
    void resize(int n)
    {
        a = vector<int>(n + 1);
    }
    void update(int pos, int val)
    {
        int n = (int)a.size() - 1;
        for (int i = pos; i <= n; i += i & (-i))
        {
            a[i] += val;
        }
    }
    int query(int pos)
    {
        int ans = 0;
        for (int i = pos; i; i -= i & (-i))
        {
            ans += a[i];
        }
        return ans;
    }
    int query(int st, int dr)
    {
        return query(dr) - query(st - 1);
    }
};
int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> q;
    while (q--)
    {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        bool sortat = true;
        for (int i = 1; i <= n; ++i)
        {
            cin >> a[i];
            if (a[i] != i)
            {
                sortat = false;
            }
        }
        if (sortat)
        {
            cout << n - 2 << '\n';
            continue;
        }
        vector<pair<int, int>> qui(n + 1);
        stack<int> s;
        bit tree;
        tree.resize(n);
        for (int i = 1; i <= n; ++i)
        {
            while (!s.empty() && a[s.top()] < a[i])
            {
                s.pop();
            }
            if (!s.empty())
            {
                qui[i].first = s.top();
            }
            if (tree.query(a[i], n) > 1)
            {
                qui[i].first = 0;
            }
            tree.update(a[i], 1);
            s.push(i);
        }
        while (!s.empty())
            s.pop();
        tree.resize(n);
        for (int i = n; i >= 1; --i)
        {
            while (!s.empty() && a[s.top()] > a[i])
            {
                s.pop();
            }
            if (!s.empty())
            {
                qui[i].second = s.top();
            }
            if (tree.query(1, a[i]) > 1)
            {
                qui[i].second = 0;
            }
            tree.update(a[i], 1);
            s.push(i);
        }
        aint lesgo;
        lesgo.resize(n);
        lesgo.init(1, 1, n);
        function<void(int, int)> upd = [&](int ind, int sign)
        {
            lesgo.update(1, 1, n, min(ind, a[ind]), max(ind, a[ind]), sign);
        };
        function<int()> count = [&]()
        {
            if (lesgo.a[1].first == 1)
            {
                return lesgo.a[1].second;
            }
            return 0;
        };
        function<void(int, int)> mySwap = [&](int i, int j)
        {
            upd(i, -1);
            upd(j, -1);
            swap(a[i], a[j]);
            upd(i, 1);
            upd(j, 1);
        };
        for (int i = 1; i <= n; ++i)
        {
            upd(i, 1);
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i)
        {
            if (qui[i].first && qui[i].second)
            {
                mySwap(qui[i].first, qui[i].second);
                ans = max(ans, count());
                mySwap(qui[i].first, qui[i].second);
            }
        }
        vector<int> pos(n + 1);
        for (int i = 1; i <= n; ++i)
        {
            pos[a[i]] = i;
        }
        for (int i = 1; i <= n; ++i)
        {
            int qui1 = i;
            int qui2 = pos[i];
            mySwap(qui1, qui2);
            ans = max(ans, count());
            mySwap(qui1, qui2);
        }
        cout << ans << '\n';
    }
}
```
Computer Science