思路

若 $c$ 是 $p$ 作 $n$ 次循环移位的幂（$c_0$ 是 $p$ 的幂，$c_1$ 是 $p$ 作一次循环移位的幂（将 $p$ 的最后一个字母移动到第一位），以此类推。

1. 由此形成的 $n$ 个排列中，初始 $p$ 的任意一个位置都有一次机会（在某一次循环移位后）出现在排列的任何位置。且对于特定位置，每次循环移位后，它的数值都会改变。例如 $1$ 有机会出现在第 $1, 2, \cdots, n$ 位各一次。
2. $c$ 里有且仅有一个 $1$。若第 $i - 1$ 次循环左移后 $p_1 = n$，则 $c_i = 1$，否则 $c_i > 1$。由于 $n$ 有且仅有一次机会出现在第一个位置，因此 $c$ 里有且仅有一个 $1$。
3. 由于每个 $c$ 值与一个排列一一对应，因此对 $c$ 数组循环移位，等价于对 $n$ 个排列的顺序循环移位。因此若原数组存在方案，则旋转后的数组也存在方案，因此可将 $c$ 旋转至 $c_1 = 1$ 时再继续考虑。现在 $c_1$ 对应的排列的第一个数一定是 $n$，对于第 $i$ 次循环左移，若 $p_1 > p_2$，则 $c_{i + 1} \le c_i$，否则 $c_{i + 1} = c_i + 1$。
4. 反之，若 $c$ 里有且仅有一个 $1$，且 $\forall i \in [1, n), c_{i + 1} - c_i \le 1$，则可以构造出满足给定 $c$ 值的 $p$（待补充，可参考)。

时间复杂度 $O(n)$。

#include <iostream>
#include <vector>
#include <algorithm>

#define endl "\n"

using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &v : a) cin >> v;

  if (count(a.begin(), a.end(), 1) != 1) {
    cout << "NO" << endl;
    return;
  }

  // begin, the elem to the begin, end
  rotate(a.begin(), find(a.begin(), a.end(), 1), a.end());

  for (int i = 1; i < n; i++)
    if (a[i] - a[i - 1] > 1) {
      cout << "NO" << endl;
      return;
    }

  cout << "YES" << endl;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}