#include <bits/stdc++.h>

using namespace std;

const int N = 1000;

int n;
int a[N];

void solve() {
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	for (int i = 1; i < n - 1; ++i) {
		if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
			cout << "YES" << endl;
			cout << i << ' ' << i + 1 << ' ' << i + 2 << endl;
			return;
		}
	}
	cout << "NO" << endl;
}

int main() {
	int T;
	cin >> T;
	while (T--)
		solve();
}

fun main() {
    val winBy = mapOf('R' to 'P', 'S' to 'R', 'P' to 'S')
    repeat(readLine()!!.toInt()) {
        val s = readLine()!!
        val maxCnt = s.groupingBy { it }.eachCount().maxBy { it.value }!!.key
        println("${winBy[maxCnt]}".repeat(s.length))
    }
}

for _ in range(int(input())):
    n, x = map(int, input().split())
    a = sorted(list(map(int, input().split())), reverse=True)
    res, cur = 0, 1
    for s in a:
        if s * cur >= x:
            res += 1
            cur = 0
        cur += 1
    print(res)
    

#include <bits/stdc++.h>

using namespace std;

const int N = int(2e5) + 9;

int n, m;
long long x, k, y;
int a[N];
int b[N];

bool upd(int l, int r, long long &res) {
    if (l > r) return true;
    bool canDel = false;
    int mx = *max_element(a + l, a + r + 1);
    int len = r - l + 1;
    if (l - 1 >= 0 && a[l - 1] > mx) canDel = true;
    if (r + 1 < n && a[r + 1] > mx) canDel = true;
    if (len < k && !canDel) return false;
    
    int need = len % k;
    res += need * y;
    len -= need;
    
    if (y * k >= x) {
        res += len / k * x;
    } else if(canDel) {
        res += len * y;
    } else {
        res += (len - k) * y + x;
    }
    
    return true;
}

int main(){
    scanf("%d %d", &n, &m);
    scanf("%lld %lld %lld", &x, &k, &y);
    for (int i = 0; i < n; ++i) scanf("%d", a + i);
    for (int i = 0; i < m; ++i) scanf("%d", b + i);
    
    long long res = 0;
    int lst = -1, posa = 0, posb = 0;
    while (posb < m) {
        while(posa < n && a[posa] != b[posb]) ++posa;
        if (posa == n) {
            puts("-1");
            return 0;
        }
        
        if (!upd(lst + 1, posa - 1, res)) {
            puts("-1");
            return 0;
        }
        
        lst = posa;
        ++posb;
    }
    
    if (!upd(lst + 1, n - 1, res)) {
        puts("-1");
        return 0;
    }
    
    printf("%lld\n", res);
    
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;
const int L = 20;

vector<int> g[2 * N];
int p[2 * N];
int up[2 * N][L];
int idx[N];
int psum[N];
int cur[N];
int tin[2 * N];
int tout[2 * N];
int T = 0;

void dfs(int x, int y)
{
	tin[x] = T++;
	p[x] = y;
	up[x][0] = y;
	for(int i = 1; i < L; i++)
		up[x][i] = up[up[x][i - 1]][i - 1];
	for(auto z : g[x])
		dfs(z, x);
	tout[x] = T++;
}

bool is_ancestor(int x, int y)
{
	return tin[x] <= tin[y] && tout[x] >= tout[y];
}

int lca(int x, int y)
{
	if(is_ancestor(x, y))
		return x;
	for(int i = L - 1; i >= 0; i--)
		if(!is_ancestor(up[x][i], y))
			x = up[x][i];
	return p[x];
}

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &idx[i]);
		idx[i]--;
	}
	for(int i = 0; i < m; i++)
		cur[i] = i;
	for(int i = 0; i < m - 1; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		--x;
		--y;
		int nidx = m + i;
		g[nidx].push_back(cur[x]);
		g[nidx].push_back(cur[y]);
		cur[x] = nidx;
	}
	int root = m * 2 - 2;
	dfs(root, root);
	for(int i = 0; i < n - 1; i++)
	{
		int t = lca(idx[i], idx[i + 1]);
		if(t < m)
			psum[0]++;
		else
			psum[t - m + 1]++;
	}
	for(int i = 0; i < m - 1; i++)
		psum[i + 1] += psum[i];
	for(int i = 0; i < m; i++)
		printf("%d\n", n - 1 - psum[i]);
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int n, m;
vector<int> p;
vector<vector<int>> val;
vector<int> who;

int getp(int a){
	return a == p[a] ? a : p[a] = getp(p[a]);
}

int main(){
	scanf("%d%d", &n, &m);
	p.resize(m);
	val.resize(m);
	who.resize(n);
	int ans = n - 1;
	forn(i, m)
		p[i] = i;
	forn(i, n){
		int x;
		scanf("%d", &x);
		--x;
		who[i] = x;
		ans -= (i && who[i] == who[i - 1]);
		val[who[i]].push_back(i);
	}
	printf("%d\n", ans);
	forn(i, m - 1){
		int v, u;
		scanf("%d%d", &v, &u);
		v = getp(v - 1), u = getp(u - 1);
		if (val[v].size() < val[u].size())
			swap(v, u);
		for (int x : val[u]){
			if (x) ans -= who[x - 1] == v;
			if (x < n - 1) ans -= who[x + 1] == v;
		}
		for (int x : val[u]){
			val[v].push_back(x);
			who[x] = v;
		}
		p[u] = v;
		printf("%d\n", ans);
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 

const int MOD = 998244353;
const int N = 500 * 1000 + 13;

string s;

int add(int a, int b){
	a += b;
	if (a >= MOD)
		a -= MOD;
	return a;
}

int mul(int a, int b){
	return a * 1ll * b % MOD;
}

struct node{
	int val[4], len;
};

node merge(const node &a, const node &b, int l, int r){
	node c;
	int na = a.len == 1 ? 0 : 1;
	int nb = b.len == 1 ? 0 : 2;
	c.len = a.len + b.len;
	c.val[0] = mul(a.val[na], b.val[nb]);
	c.val[1] = mul(a.val[na], b.val[3]);
	c.val[2] = mul(a.val[3], b.val[nb]);
	c.val[3] = mul(a.val[3], b.val[3]);
	if (l == 1){
		na = a.len == 1 ? 2 : 0;
		nb = b.len == 1 ? 1 : 0;
		c.val[na + nb] = add(c.val[na + nb], mul(mul(a.val[0], b.val[0]), 19 - (l * 10 + r)));
		c.val[1 + na] = add(c.val[1 + na], mul(mul(a.val[0], b.val[1]), 19 - (l * 10 + r)));
		c.val[2 + nb] = add(c.val[2 + nb], mul(mul(a.val[2], b.val[0]), 19 - (l * 10 + r)));
		c.val[3] = add(c.val[3], mul(mul(a.val[2], b.val[1]), 19 - (l * 10 + r)));
	}
	return c;
}

node t[4 * N];

void build(int v, int l, int r){
	t[v].len = r - l;
	if (l == r - 1){
		t[v].val[0] = 1;
		t[v].val[3] = s[l] + 1;
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m);
	build(v * 2 + 1, m, r);
	t[v] = merge(t[v * 2], t[v * 2 + 1], s[m - 1], s[m]);
}

void upd(int v, int l, int r, int x, int val){
	if (l == r - 1){
		s[l] = val;
		t[v].val[3] = s[l] + 1;
		return;
	}
	int m = (l + r) / 2;
	if (x < m)
		upd(v * 2, l, m, x, val);
	else
		upd(v * 2 + 1, m, r, x, val);
	t[v] = merge(t[v * 2], t[v * 2 + 1], s[m - 1], s[m]);
}

int main(){
	int n, m;

	scanf("%d%d", &n, &m);
	static char buf[N];
	scanf("%s", buf);
	s = buf;
	forn(i, n) s[i] -= '0';
	
	memset(t, 0, sizeof(t));
	build(1, 0, n);
	
	forn(i, m){
		int x, v;
		scanf("%d%d", &x, &v);
		--x;
		upd(1, 0, n, x, v);
		printf("%d\n", t[1].val[3]);
	}
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(5e5) + 9;
const int MOD = 998244353;

int mul(int a, int b) {
    return (a * 1LL * b) % MOD;
}

void add(int &a, int x) {
    a += x;
    a %= MOD;
}

int bp(int a, int n) {
    int res = 1;
    for (; n > 0; n >>= 1) {
        if (n & 1) res = mul(res, a);
        a = mul(a, a);
    }
    return res;
}

int inv(int a) {
    int ia = bp(a, MOD - 2);
    assert(mul(a, ia) == 1);
    return ia;
}

int n, m;
string s;
int dp[N][10];
int idp[N][10];
set <pair<int, int> > lr;
int res = 1;

void updRes(int l, int r, int c) {
    assert(l <= r);
    if (c == 1) {
        assert(!lr.count(make_pair(l, r)));
        lr.insert(make_pair(l, r));
        res = mul(res, dp[r - l + (r + 1 != n)][r + 1 == n? 1 : s[r + 1] - '0']);
    } else {
        assert(lr.count(make_pair(l, r)));
        lr.erase(make_pair(l, r));
        res = mul(res, inv(dp[r - l + (r + 1 != n)][r + 1 == n? 1 : s[r + 1] - '0']));
    }
}

void getLR(int &l, int &r, int pos) {
    l = r = -1;
    auto it = lr.lower_bound(make_pair(pos, n));
    if(it == lr.begin()) return;
    --it;
    if(!(it->first <= pos && pos <= it->second)) return;
    l = it->first, r = it->second;
}

char buf[N];
int main(){
    scanf("%d %d\n", &n, &m);
    scanf("%s", buf);
    s = string(buf);
    for (int i = 0; i <= 9; ++i) {
        dp[0][i] = i + 1; //idp[0][i] = inv(dp[0][i]);
        dp[1][i] = 2 * (i + 1) + (9 - i); //idp[1][i] = inv(dp[1][i]);
    }
    for (int i = 2; i < N; ++i)
        for (int j = 0; j <= 9; ++j) {
            dp[i][j] = (2LL * dp[i - 1][j] + 8LL * dp[i - 2][j]) % MOD;
            //idp[i][j] = inv(dp[i][j]);
        }
    for (int i = 0; i < N; ++i) for(int j = 0; j < 10; ++j) assert(dp[i][j] != 0);
    for (int l = 0; l < n; ) {
        int r = l;
        while(r < n && s[r] == '1') ++r;
        res = mul(res, dp[r - l - (r == n)][r == n? 1 : s[r] - '0']);
        if (l != r) lr.insert(make_pair(l, r - 1));
        l = r + 1;
    }
    
    for (int i = 0; i < m; ++i) {
        int pos;
        char x;
        scanf("%d %c\n", &pos, &x);
        --pos;
        if (x == '1') {
            if (s[pos] != '1'){ 
                int l1, r1, l2, r2;
                getLR(l1, r1, pos - 1);
                getLR(l2, r2, pos + 1);
                
                int l = pos, r = pos;
                if (l1 != -1) {
                    assert(r1 == pos - 1);
                    updRes(l1, r1, -1);
                    l = l1;
                } else {
                    res = mul(res, inv(dp[0][s[pos] - '0']));
                }
                
                if (l2 != -1) {
                    assert(l2 == pos + 1);
                    updRes(l2, r2, -1);
                    r = r2;
                } else {
                    if (pos + 1 != n) res = mul(res, inv(dp[0][s[pos + 1] - '0']));
                }
                
                s[pos] = x;
                updRes(l, r, 1);
            }
        } else {
            if (s[pos] != '1') {
                if (pos - 1 >= 0 && s[pos - 1] == '1') {
                    int l, r;
                    getLR(l, r, pos - 1);
                    updRes(l, r, -1);
                    s[pos] = x;
                    updRes(l, r, 1);
                } else {
                    res = mul(res, dp[0][x - '0']);
                    res = mul(res, inv(dp[0][s[pos] - '0']));
                    s[pos] = x;
                }
            } else {
                int l, r;
                getLR(l, r, pos);
                assert(l != -1 && r != -1);
                
                updRes(l, r, -1);
                s[pos] = x;
                if (l == r) {
                    res = mul(res, dp[0][s[pos] - '0']);
                    if (pos + 1 < n) res = mul(res, dp[0][s[pos + 1] - '0']);
                } else if (pos == l) {
                    res = mul(res, dp[0][s[pos] - '0']);
                    updRes(l + 1, r, 1);
                } else if (pos == r) {
                    if (pos + 1 != n) res = mul(res, dp[0][s[pos + 1] - '0']);
                    updRes(l, r - 1, 1);
                } else {
                    updRes(l, pos - 1, 1);
                    updRes(pos + 1, r, 1);
                }
            }
            
        }
        printf("%d\n", res);
    }
}

At first, let's say that the expected value is equal to the average of total earnings over all positions and is equal to the sum of earnings over all positions divided by $$$n$$$. So we can trasition to minimizing the sum.

Let's learn how to solve the task for some fixed $$$k$$$. Fix some arrangement and rotate the rooms so that the last room contains a mimic. So now you have $$$cnt_1$$$ regular chests, then a single mimic, $$$cnt_2$$$ regular chests, single mimic, $$$\dots$$$, $$$cnt_k$$$ regular chests, single mimic. All $$$cnt_i \ge 0$$$ and $$$\sum \limits_{i=1}^{k} cnt_i = n - k$$$.

Take a look at some of these intervals of length $$$cnt_i$$$. The last chest in the interval is taken from $$$cnt_i$$$ starting positions, the second-to-last is taken $$$cnt_i - 1$$$ times and so on.

Now let's find the optimal way to choose $$$cnt_i$$$. Fix some values of $$$cnt_i$$$. Take a look at the smallest of these values and the largest of them. Let the values be $$$x$$$ and $$$y$$$. If they differ by at least $$$2$$$ ($$$x \le y - 2$$$), then the smaller result can always be achieved by moving a regular chest from the larger one to the smaller one.

Now we have all $$$cnt_i$$$ set now. The only thing left is to assign chests optimally. Write down the union of all the coefficient sequences from all the intervals $$$\bigcup \limits_{i=1}^{n-k} [1, \dots, cnt_i-1, cnt_i]$$$ and sort them in the non-decreasing order. It's easy to show that the chests should be sorted in the non-increasing order (really classical thing, you can try proving that by showing that any other arrangement can easily be improved once again).

That allows us to write a solution in $$$O(n^2)$$$. Sort all the chests in the beginning, after that for some $$$k$$$ multiply the value of the $$$i$$$-th chest by $$$\lfloor \frac{i}{k} \rfloor$$$ and sum up the results.

Finally, let's speed this up with prefix sums. Notice that the first $$$k$$$ values are multiplied by $$$0$$$, the second $$$k$$$ values — by $$$1$$$ and so on. If $$$n$$$ is not divisible by $$$k$$$, then the last block just has length smaller than $$$k$$$. Thus, we can calculate the answer for some $$$k$$$ in $$$O(\frac{n}{k})$$$. And that's equal to $$$O(\sum \limits_{k=1}^{n} \frac{n}{k})$$$ = $$$O(n \log n)$$$.

Overall complexity: $$$O(n \log n)$$$.

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int MOD = 998244353;

int add(int a, int b){
	a += b;
	if (a >= MOD)
		a -= MOD;
	if (a < 0)
		a += MOD;
	return a;
}

int mul(int a, int b){
	return a * 1ll * b % MOD;
}

int binpow(int a, int b){
	int res = 1;
	while (b){
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}

vector<int> pr;

int main() {
	int n;
	scanf("%d", &n);
	vector<int> c(n);
	forn(i, n)
		scanf("%d", &c[i]);
	sort(c.begin(), c.end(), greater<int>());
	pr.push_back(0);
	forn(i, n)
		pr.push_back(add(pr.back(), c[i]));
	
	int invn = binpow(n, MOD - 2);
	for (int k = 1; k <= n; ++k){
		int ans = 0;
		for (int i = 0, j = 0; i < n; i += k, ++j)
			ans = add(ans, mul(j, add(pr[min(n, i + k)], -pr[i])));
		printf("%d ", mul(ans, invn));
	}
	puts("");
	
	return 0;
}