#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef map<int, int> mpii;
typedef unordered_map<int, int> umpii;
#define pb(v) push_back(v)
int inf = 1e9;
int mod = 1e9 + 7;
double eps = 1e-9;
int dr[] = {-1, 0, 0, 1};
int dc[] = {0, 1, -1, 0};
/*...................................................*/
int dp[100010][2];
int fn(vii &a, int i, int ch, set<int> &markedL, set<int> &markedR, int call)
{
if (dp[i][ch] != -1)
return dp[i][ch];
int idx = a[i].second;
if (!ch)
markedL.insert(-idx);
else
markedR.insert(idx);
int mn = inf, mx = -1;
if (!markedR.empty())
mn = *markedR.begin();
if (!markedL.empty())
mx = -(*markedL.begin());
// cout << "\nRecursive Call: " << call << '\n';
// cout << "\nIndices which have been marked Left: \n";
// for(auto it: markedL)
// cout << it << ' ';
// cout << "\nIndices which have been marked Right: \n";
// for(auto it: markedR)
// cout << it << ' ';
// cout << '\n';
//cout << "mn: " << mn << " mx: " << mx << '\n';
bool f = 0;
for (int j = i + 1; !f && j < a.size(); j++)
{
int id = a[j].second;
if (mx < id && id < mn) // check if 'id' has already been marked or not
f = 1, dp[i][ch] = 1 + min(fn(a, j, 0, markedL, markedR, call + 1), fn(a, j, 1, markedL, markedR, call + 1));
}
if (!ch)
markedL.erase(-idx);
else
markedR.erase(idx);
if (!f)
return dp[i][ch] = 1;
return dp[i][ch];
}
int main()
{
int t, n, m, i, j;
cin >> t;
int tc = t;
while (t--)
{
cin >> n;
vii a(n);
for (i = 0; i < n; i++)
dp[i][0] = dp[i][1] = -1;
for (i = 0; i < n; i++)
{
ll x;
cin >> x;
a[i] = {x, i};
}
sort(a.begin(), a.end(), greater<>());
set<int> sl, sr;
cout << min(fn(a, 0, 0, sl, sr, 0), fn(a, 0, 1, sl, sr, 0)) << '\n';
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiBwYWlyPGxsLCBsbD4gcGxsOwp0eXBlZGVmIHZlY3RvcjxwbGw+IHZwbGw7CnR5cGVkZWYgcGFpcjxpbnQsIGludD4gaWk7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgdmVjdG9yPGxsPiB2bGw7CnR5cGVkZWYgdmVjdG9yPGlpPiB2aWk7CnR5cGVkZWYgdmVjdG9yPHZpPiB2dmk7CnR5cGVkZWYgdmVjdG9yPHZpaT4gdnZpaTsKdHlwZWRlZiBtYXA8aW50LCBpbnQ+IG1waWk7CnR5cGVkZWYgdW5vcmRlcmVkX21hcDxpbnQsIGludD4gdW1waWk7CiNkZWZpbmUgcGIodikgcHVzaF9iYWNrKHYpCgppbnQgaW5mID0gMWU5OwppbnQgbW9kID0gMWU5ICsgNzsKZG91YmxlIGVwcyA9IDFlLTk7CmludCBkcltdID0gey0xLCAwLCAwLCAxfTsKaW50IGRjW10gPSB7MCwgMSwgLTEsIDB9OwoKLyouLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4qLwoKaW50IGRwWzEwMDAxMF1bMl07CgppbnQgZm4odmlpICZhLCBpbnQgaSwgaW50IGNoLCBzZXQ8aW50PiAmbWFya2VkTCwgc2V0PGludD4gJm1hcmtlZFIsIGludCBjYWxsKQp7CiAgICBpZiAoZHBbaV1bY2hdICE9IC0xKQogICAgICAgIHJldHVybiBkcFtpXVtjaF07CgogICAgaW50IGlkeCA9IGFbaV0uc2Vjb25kOwogICAgaWYgKCFjaCkKICAgICAgICBtYXJrZWRMLmluc2VydCgtaWR4KTsKICAgIGVsc2UKICAgICAgICBtYXJrZWRSLmluc2VydChpZHgpOwoKICAgIGludCBtbiA9IGluZiwgbXggPSAtMTsKICAgIGlmICghbWFya2VkUi5lbXB0eSgpKQogICAgICAgIG1uID0gKm1hcmtlZFIuYmVnaW4oKTsKCiAgICBpZiAoIW1hcmtlZEwuZW1wdHkoKSkKICAgICAgICBteCA9IC0oKm1hcmtlZEwuYmVnaW4oKSk7CgogICAgLy8gY291dCA8PCAiXG5SZWN1cnNpdmUgQ2FsbDogIiA8PCBjYWxsIDw8ICdcbic7CiAgICAvLyBjb3V0IDw8ICJcbkluZGljZXMgd2hpY2ggaGF2ZSBiZWVuIG1hcmtlZCBMZWZ0OiBcbiI7CiAgICAvLyBmb3IoYXV0byBpdDogbWFya2VkTCkKICAgIC8vIGNvdXQgPDwgaXQgPDwgJyAnOwoKICAgIC8vIGNvdXQgPDwgIlxuSW5kaWNlcyB3aGljaCBoYXZlIGJlZW4gbWFya2VkIFJpZ2h0OiBcbiI7CiAgICAvLyBmb3IoYXV0byBpdDogbWFya2VkUikKICAgIC8vIGNvdXQgPDwgaXQgPDwgJyAnOwogICAgLy8gY291dCA8PCAnXG4nOwoKICAgIC8vY291dCA8PCAibW46ICIgPDwgbW4gPDwgIiBteDogIiA8PCBteCA8PCAnXG4nOwogICAgYm9vbCBmID0gMDsKICAgIGZvciAoaW50IGogPSBpICsgMTsgIWYgJiYgaiA8IGEuc2l6ZSgpOyBqKyspCiAgICB7CiAgICAgICAgaW50IGlkID0gYVtqXS5zZWNvbmQ7CiAgICAgICAgaWYgKG14IDwgaWQgJiYgaWQgPCBtbikgLy8gY2hlY2sgaWYgJ2lkJyBoYXMgYWxyZWFkeSBiZWVuIG1hcmtlZCBvciBub3QKICAgICAgICAgICAgZiA9IDEsIGRwW2ldW2NoXSA9IDEgKyBtaW4oZm4oYSwgaiwgMCwgbWFya2VkTCwgbWFya2VkUiwgY2FsbCArIDEpLCBmbihhLCBqLCAxLCBtYXJrZWRMLCBtYXJrZWRSLCBjYWxsICsgMSkpOwogICAgfQoKICAgIGlmICghY2gpCiAgICAgICAgbWFya2VkTC5lcmFzZSgtaWR4KTsKICAgIGVsc2UKICAgICAgICBtYXJrZWRSLmVyYXNlKGlkeCk7CgogICAgaWYgKCFmKQogICAgICAgIHJldHVybiBkcFtpXVtjaF0gPSAxOwogICAgcmV0dXJuIGRwW2ldW2NoXTsKfQppbnQgbWFpbigpCnsKICAgIGludCB0LCBuLCBtLCBpLCBqOwoKICAgIGNpbiA+PiB0OwogICAgaW50IHRjID0gdDsKICAgIHdoaWxlICh0LS0pCiAgICB7CiAgICAgICAgY2luID4+IG47CiAgICAgICAgdmlpIGEobik7CgogICAgICAgIGZvciAoaSA9IDA7IGkgPCBuOyBpKyspCiAgICAgICAgICAgIGRwW2ldWzBdID0gZHBbaV1bMV0gPSAtMTsKCiAgICAgICAgZm9yIChpID0gMDsgaSA8IG47IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGxsIHg7CiAgICAgICAgICAgIGNpbiA+PiB4OwogICAgICAgICAgICBhW2ldID0ge3gsIGl9OwogICAgICAgIH0KCiAgICAgICAgc29ydChhLmJlZ2luKCksIGEuZW5kKCksIGdyZWF0ZXI8PigpKTsKCiAgICAgICAgc2V0PGludD4gc2wsIHNyOwogICAgICAgIGNvdXQgPDwgbWluKGZuKGEsIDAsIDAsIHNsLCBzciwgMCksIGZuKGEsIDAsIDEsIHNsLCBzciwgMCkpIDw8ICdcbic7CiAgICB9CiAgICByZXR1cm4gMDsKfQ==