我学的一知半解的，有什么问题欢迎指出。

下面是题目复述：

Description

A championship is held in Berland, in which n players participate. The player with the number i has ai (ai≥1) tokens.

The championship consists of n−1 games, which are played according to the following rules:

in each game, two random players with non-zero tokens are selected; the player with more tokens is considered the winner of the game (in case of a tie, the winner is chosen randomly); the winning player takes all of the loser's tokens; The last player with non-zero tokens is the winner of the championship.

All random decisions that are made during the championship are made equally probable and independently.

For example, if n=4, a=[1,2,4,3], then one of the options for the game (there could be other options) is:

during the first game, the first and fourth players were selected. The fourth player has more tokens, so he takes the first player's tokens. Now a=[0,2,4,4]; during the second game, the fourth and third players were selected. They have the same number of tokens, but in a random way, the third player is the winner. Now a=[0,2,8,0]; during the third game, the second and third players were selected. The third player has more tokens, so he takes the second player's tokens. Now a=[0,0,10,0]; the third player is declared the winner of the championship. Championship winners will receive personalized prizes. Therefore, the judges want to know in advance which players have a chance of winning, i.e have a non-zero probability of winning the championship. You have been asked to find all such players.

Input

The first line contains one integer t (1≤t≤104) — the number of test cases. Then t test cases follow.

The first line of each test case consists of one positive integer n (1≤n≤2⋅105) — the number of players in the championship.

The second line of each test case contains n positive integers a1,a2,…,an (1≤ai≤109) — the number of tokens the players have.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.

Output

For each test case, print the number of players who have a nonzero probability of winning the championship. On the next line print the numbers of these players in increasing order. Players are numbered starting from one in the order in which they appear in the input.

Example

input

1 2 4 3

1 1 1 1 1

output

2 3 4

1 2 3 4 5

题目大意：

有n个人比赛，每个人有不同的初始分数，分数高的人获得胜利，如果分数一样的话胜利的机会对半分。最后统计在所有比赛流程中有可能获胜的人的个数和编号。

（全篇翻译我实在无能为力，建议去问万能的翻译软件吧）

分析过程：

首先，在整个过程中，是只要分数比别人高或者相同都可以算是胜利，所以可以将数列全部升序排列。
然后，如果在一个人的分数加上所有比他小的数字依然不过的时候，就可以将他和比他小的所有人排除掉了。计算一个人的分数和比他小的所有数字的总和的时候，即为计算前缀和。
接着，因为要排序，所以我采用了结构的方式保存的前面所有人的序号。并且用新的数组储存计算出来的人的编号。
最后，把新的数组排序就可以啦。

PS.记得虽然数组类型不超int，但是前缀和会超int，记得更换数据类型。

下面是AC代码：

#include<cstdio>
#include<cmath>
using namespace std;
int t;

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        long long n,m;
        scanf("%lld",&n);
        int fin=0;
        for(long long i=1; i<=cbrt(n); i++)//cbrtÁ¢·½¸ù
        {
            m=n-(i*i*i);
            long long tmp=cbrt(m);
            if((tmp*tmp*tmp)==m&&tmp>0)
            {
                fin=1;
                break;
            }
        }
        if(fin==1)
            printf("YES\n");
        else printf("NO\n");

    }
    return 0;
｝

【题解】前缀和——Accidental Victory

下面是题目复述：

题目大意：

分析过程：

下面是AC代码：