1907F - Shift and Reverse - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxi(v, n) *max_element(v, v + n)
#define mini(v, n) *min_element(v, v + n)
const ll mod = 1e9 + 7;
ll seg[4 * 100000];
ll lazy[4 * 100000];
void build(ll ind, ll low, ll high, vector<ll> &v) // max query
{
  if (low == high)
  {
    seg[ind] = v[low];
    return;
  }
  ll mid = low + (high - low) / 2;
  build(2 * ind + 1, low, mid, v);
  build(2 * ind + 2, mid + 1, high, v);
  seg[ind] = max(seg[2 * ind + 1], seg[2 * ind + 2]);
}
ll query(ll ind, ll low, ll high, ll l, ll r, vector<ll> &v) // max query
{
  if (low >= l && high <= r)
    return seg[ind];
  if (l > high || r < low)
    return INT_MIN;
  ll mid = low + (high - low) / 2;
  ll left = query(2 * ind + 1, low, mid, l, r, v);
  ll right = query(2 * ind + 2, mid + 1, high, l, r, v);
  return max(left, right);
}
void pointupdate(ll ind, ll low, ll high, ll node, ll val) // max query
{
  if (low == high)
    seg[ind] = val;
  else
  {
    ll mid = low + (high - low) / 2;
    if (node <= mid && node >= low)
      pointupdate(2 * ind + 1, low, mid, node, val);
    else
      pointupdate(2 * ind + 2, mid + 1, high, node, val);

    seg[ind] = max(seg[2 * ind + 1], seg[2 * ind + 2]);
  }
}
void rangeupdate(ll ind, ll low, ll high, ll l, ll r, ll val) // sum query
{
  if (lazy[ind] != 0)
  {
    seg[ind] = (high - low + 1) * lazy[ind];
    if (low != high)
    {
      lazy[2 * ind + 1] += lazy[ind];
      lazy[2 * ind + 2] += lazy[ind];
    }
    lazy[ind] = 0;
  }
  if (l > high || r < low || low > high)
    return;
  if (l <= low && high <= r)
  {
    seg[ind] += (high - low + 1) * val;
    if (high != low)
    {
      lazy[2 * ind + 1] += val;
      lazy[2 * ind + 2] += val;
    }
    return;
  }
  ll mid = low + (high - low) / 2;
  rangeupdate(2 * ind + 1, low, mid, l, r, val);
  rangeupdate(2 * ind + 2, mid + 1, high, l, r, val);
  seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
}
ll queryafter(ll ind, ll low, ll high, ll l, ll r, vector<ll> &v) // sumquery
{
  if (lazy[ind] != 0)
  {
    seg[ind] += (high - low + 1) * lazy[ind];
    if (low != high)
    {
      lazy[2 * ind + 1] += lazy[ind];
      lazy[2 * ind + 2] += lazy[ind];
    }
    lazy[ind] = 0;
  }
  if (low >= l && high <= r)
    return seg[ind];
  if (l > high || r < low || low > high)
    return 0;
  ll mid = low + (high - low) / 2;
  ll left = queryafter(2 * ind + 1, low, mid, l, r, v);
  ll right = queryafter(2 * ind + 2, mid + 1, high, l, r, v);
  return left + right;
}
ll modInverse(ll A, ll M)
{
  ll m0 = M;
  ll y = 0, x = 1;
  if (M == 1)
    return 0;
  while (A > 1)
  {
    ll q = A / M;
    ll t = M;
    M = A % M, A = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0)
    x += m0;
  return x;
}
void PrefixSum(ll arr[], ll n, ll pre[])
{
  pre[0] = arr[0];
  for (ll i = 1; i < n; i++)
    pre[i] = pre[i - 1] + arr[i];
}
void SuffixSum(ll arr[], ll n, ll suff[])
{
  suff[n - 1] = arr[n - 1];
  for (ll i = n - 2; i >= 0; i--)
    suff[i] = suff[i + 1] + arr[i];
}
ll odd(ll x)
{
  if (x % 2 == 0)
  {
    return 1;
  }
  return 0;
}
bool sort(vector<ll> &arr, ll n)
{
  if (n == 0 || n == 1)
    return true;

  for (ll i = 1; i < n; i++)
    if (arr[i - 1] > arr[i])
      return false;

  return true;
}
bool rsort(vector<ll> &arr, ll n)
{

  if (n == 0 || n == 1)
    return true;

  for (ll i = 1; i < n; i++)
    if (arr[i - 1] < arr[i])
      return false;

  return true;
}
ll fun(vector<ll> &v, ll mx, ll mi, ll n)
{
  vector<ll> a, b, c, d;
  ll mi1 = 0;
  ll mi2 = 0;
  ll ma1 = 0;
  ll ma2 = 0;
  for (ll i = 0; i < n; i++)
    if (v[i] == mx)
    {
      ma1 = i;
      break;
    }
  for (ll i = 0; i < n; i++)
    if (v[i] == mi)
    {
      mi1 = i;
      break;
    }
  for (ll i = n - 1; i >= 0; i--)
    if (v[i] == mx)
    {
      ma2 = i;
      break;
    }
  for (ll i = n - 1; i >= 0; i--)
    if (v[i] == mi)
    {
      mi2 = i;
      break;
    }
  //  cout << ma1 << " " << ma2 << " " << mi1 << " " << mi2 << endl;
  ll ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0;

  for (ll i = ma1 + 1; i < n; i++)
    a.push_back(v[i]);
  for (ll i = 0; i <= ma1; i++)
    a.push_back(v[i]);
  ans1 = n - ma1 - 1;
  if (sort(a, n))
    ans1 = ans1;
  else
    ans1 = INT_MAX;

  for (ll i = ma2 + 1; i < n; i++)
    b.push_back(v[i]);
  for (ll i = 0; i <= ma2; i++)
    b.push_back(v[i]);
  ans2 = n - ma2 - 1;
  if (sort(b, n))
    ans2 = ans2;
  else
    ans2 = INT_MAX;

  for (ll i = mi1 + 1; i < n; i++)
    c.push_back(v[i]);
  for (ll i = 0; i <= mi1; i++)
    c.push_back(v[i]);
  ans3 = n - mi1 - 1;
  if (rsort(c, n))
    ans3 = ans3 + 1;
  else
    ans3 = INT_MAX;

  for (ll i = mi2 + 1; i < n; i++)
    d.push_back(v[i]);
  for (ll i = 0; i <= mi2; i++)
    d.push_back(v[i]);
  ans4 = n - mi2 - 1;
  if (rsort(d, n))
    ans4 = ans4 + 1;
  else
    ans4 = INT_MAX;

  // cout << ans1 << " " << ans2 << " " << ans3 << " " << ans4 << endl;
  ll myans = min(ans1, min(ans2, min(ans3, ans4)));
  return myans;
}
bool sort1(vector<ll> &arr, ll x, ll y)
{
  if (y - x == 0 || y - x == 1)
    return true;

  for (ll i = x + 1; i <= y; i++)
    if (arr[i - 1] > arr[i])
      return false;

  return true;
}
bool rsort1(vector<ll> &arr, ll x, ll y)
{

  if (y - x == 0 || y - x == 1)
    return true;

  for (ll i = x + 1; i <= y; i++)
    if (arr[i - 1] < arr[i])
      return false;

  return true;
}
void solve(int x)
{
  ll n;
  cin >> n;
  vector<ll> v(n);
  ll mx = INT_MIN;
  ll mi = INT_MAX;
  for (ll i = 0; i < n; i++)
    cin >> v[i], mx = max(mx, v[i]), mi = min(mi, v[i]);
  ll ct1 = 0;
  ll ct2 = 0;
  for (ll i = 0; i < n; i++)
  {
    if (v[i] == mx)
      ct1++;
    if (v[i] == mi)
      ct2++;
  }
  if (x == -1)
  {
    cout << n << "|";
    for (int i = 0; i < n; i++)
      cout << v[i] << "|";
    cout << endl;
  }
  ll ans = INT_MAX;
  if (ct1 >= 2)
  {
    // cout<<1;
    ll c1 = 0, c2 = 0;
    for (ll i = 0; i < n; i++)
      if (v[i] == mx)
        c1++;
      else
        break;
    for (ll i = n - 1; i >= 0; i--)
      if (v[i] == mx)
        c2++;
      else
        break;
    if (c1 + c2 == ct1 && c1 != 0 && c2 != 0)
      if (sort1(v, c1, n - c2 - 1))
      {
        ans = n - c1;
      }
      else if (rsort1(v, c1, n - c2 - 1))
      {
        ans = n - c2;
      }
      else
      {
      }
    // cout<<ans<<endl;
  }
  //  cout<<ans<<endl;
  if (ct2 >= 2)
  {
    //  cout<<1;
    ll c1 = 0, c2 = 0;
    for (ll i = 0; i < n; i++)
      if (v[i] == mi)
        c1++;
      else
        break;
    for (ll i = n - 1; i >= 0; i--)
      if (v[i] == mi)
        c2++;
      else
        break;
    //  cout << c1 << " " << c2 << endl;
    if (c1 + c2 == ct1 && c1 != 0 && c2 != 0)
      if (sort1(v, c1, n - c2 - 1))
      {
        ans = min(c2, ans);
      }
      else if (rsort1(v, c1, n - c2 - 1))
      {
        ans = min(c2 + 1, ans);
      }
      else
      {
      }
  }
  // cout<<ans<<endl;
  // if (x == -1)
  // {
  //   cout << n << "|";
  //   for (int i = 0; i < n; i++)
  //     cout << v[i] << "|";
  //   cout << endl;
  // }
  if (sort(v, n))
  {
    cout << 0 << endl;
    return;
  }
  if (rsort(v, n))
  {
    cout << 1 << endl;
    return;
  }
  ll ch = 0;
  for (ll i = 1; i < n; i++)
  {
    if (v[i] == mi && v[i - 1] == mx)
      ch = 1;
    if (v[i] == mx && v[i - 1] == mi)
      ch = 1;
  }
  if (!ch)
  {
    cout << -1 << endl;
    return;
  }
  ll ans1 = fun(v, mx, mi, n);
  reverse(v.begin(), v.end());
  ll ans2 = fun(v, mx, mi, n) + 1;
  //  cout << ans1 << " " << ans2 << endl;
  if (min(ans1, ans2) == INT_MAX)
    cout << -1 << endl;
  else
    cout << min(ans1, min(ans2, ans)) << endl;
  // vector<ll> a, b, c, d;
  // ll mi1 = 0;
  // ll mi2 = 0;
  // ll ma1 = 0;
  // ll ma2 = 0;
  // for (ll i = 0; i < n; i++)
  //   if (v[i] == mx)
  //   {
  //     ma1 = i;
  //     break;
  //   }
  // for (ll i = 0; i < n; i++)
  //   if (v[i] == mi)
  //   {
  //     mi1 = i;
  //     break;
  //   }
  // for (ll i = n - 1; i >= 0; i--)
  //   if (v[i] == mx)
  //   {
  //     ma2 = i;
  //     break;
  //   }
  // for (ll i = n - 1; i >= 0; i--)
  //   if (v[i] == mi)
  //   {
  //     mi2 = i;
  //     break;
  //   }
  // //  cout << ma1 << " " << ma2 << " " << mi1 << " " << mi2 << endl;
  // ll ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0;

  // for (ll i = ma1 + 1; i < n; i++)
  //   a.push_back(v[i]);
  // for (ll i = 0; i <= ma1; i++)
  //   a.push_back(v[i]);
  // ans1 = n - ma1 - 1;
  // if (sort(a, n))
  //   ans1 = ans1;
  // else
  //   ans1 = INT_MAX;

  // for (ll i = ma2 + 1; i < n; i++)
  //   b.push_back(v[i]);
  // for (ll i = 0; i <= ma2; i++)
  //   b.push_back(v[i]);
  // ans2 = n - ma2 - 1;
  // if (sort(b, n))
  //   ans2 = ans2;
  // else
  //   ans2 = INT_MAX;

  // for (ll i = mi1 + 1; i < n; i++)
  //   c.push_back(v[i]);
  // for (ll i = 0; i <= mi1; i++)
  //   c.push_back(v[i]);
  // ans3 = n - mi1 - 1;
  // if (rsort(c, n))
  //   ans3 = ans3 + 1;
  // else
  //   ans3 = INT_MAX;

  // for (ll i = mi2 + 1; i < n; i++)
  //   d.push_back(v[i]);
  // for (ll i = 0; i <= mi2; i++)
  //   d.push_back(v[i]);
  // ans4 = n - mi2 - 1;
  // if (rsort(d, n))
  //   ans4 = ans4 + 1;
  // else
  //   ans4 = INT_MAX;

  // // cout << ans1 << " " << ans2 << " " << ans3 << " " << ans4 << endl;
  // ll myans = min(ans1, min(ans2, min(ans3, ans4)));
  // if (myans == INT_MAX)
  //   cout << -1 << endl;
  // else
  //   cout << myans << endl;
}
int main()
{
  ll t;
  cin >> t;
  int testmain = t;
  while (t--)
  {
    solve(testmain - t);
  }
  return 0;
}