# D. Permutation Graph

link : https://codeforces.com/problemset/problem/1696/D

tóm tắt đề : cho 1 hoán vị n số, nếu min và max [i...j] nằm ở 2 đầu mút thì có cạnh (i, j) với trọng số 1, tìm minpath 1 -> n.

+ suy nghĩ 1 : khả năng cao là bfs, tìm cách xét mỗi cạnh đúng 1 lần

+ suy nghĩ 2 : dùng kĩ thuật tịnh tiến deque + segment là có thể thực hiện ý tưởng

sml, do code dài quá phải xem hint, dcm non thế này thì chỉ nên làm dev quèn sống qua ngày =))))

:::spoiler

#include<bits/stdc++.h>
#define pii pair<int, int>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define rev(i, a, b) for (int i = (a); i >= (b); --i)
#define X first
#define Y second

using namespace std;
const int mxn = 5e5 + 5;
int a[mxn];
int mi[20][mxn], mx[20][mxn];

int gmi(int l, int r)
{
    int x = log2(r - l + 1);
    if (a[mi[x][l]] < a[mi[x][r - (1 << x) + 1]]) return mi[x][l];
    return mi[x][r - (1 << x) + 1];
}

int gmx(int l, int r)
{
    int x = log2(r - l + 1);
    if (a[mx[x][l]] > a[mx[x][r - (1 << x) + 1]]) return mx[x][l];
    return mx[x][r - (1 << x) + 1];
}

int solve (int l, int r)
{
    int a = gmi(l, r), b = gmx(l, r);
    if (a == l && b == r) return 1;
    if (b == l && a == r) return 1;

    int x;
    if (a == l || a == r)
        x = b;
    else x = a;

    return (solve(l, x) + solve(x, r));
}

int main() {
    //freopen("D:\\test.txt", "r", stdin);
    //freopen("D:\\test2.txt", "w", stdout);
    int t; cin >> t;
    while(t--)
    {
        int n; cin >> n;
        rep(i, 1, n) cin >> a[i];
        rep(i, 1, n) mx[0][i] = mi[0][i] = i;

        rep(i, 1, 18) rep(u, 1, n)
        {
            if (a[mx[i - 1][u]] > a[mx[i - 1][u + (1 << (i - 1))]])
                mx[i][u] = mx[i - 1][u];
            else mx[i][u] = mx[i - 1][u + (1 << (i - 1))];

            if (a[mi[i - 1][u]] < a[mi[i - 1][u + (1 << (i - 1))]])
                mi[i][u] = mi[i - 1][u];
            else mi[i][u] = mi[i - 1][u + (1 << (i - 1))];
        }

        if (n == 1) cout << "0\n";
        else cout << solve(1, n) << "\n";
    }
}

:::