/* Counts 213 occurrences in O(n log n). Does a linear sweep through the permutation from top to bottom, using a Segment Tree for bookkeeping. NOTE: Assumes that the input values are distinct. */ #include using namespace std; #define rep(i,a,b) for (auto i=(a); i<(b); ++i) #define iter(it,c) for (auto it = (c).begin(); it != (c).end(); ++it) typedef pair ii; typedef vector vi; typedef vector vii; typedef vector vvi; typedef long long ll; const int INF = 2147483647; #define MAXN (500000) struct node { int right_under; ll ascents_covering; ll lazy_add_x, lazy_add_c; } st[4*MAXN]; void build(int at, int l, int r) { if (l > r) return; st[at].right_under = 0; st[at].ascents_covering = 0; st[at].lazy_add_x = 0; st[at].lazy_add_c = 0; if (l < r) { int m = (l+r)/2; build(at*2+1, l, m); build(at*2+2, m+1, r); } } void propagate(int at, int l, int r) { if (l > r || (st[at].lazy_add_x == 0 && st[at].lazy_add_c == 0)) return; int m = (l+r)/2; ll add_x = st[at].lazy_add_x, add_c = st[at].lazy_add_c; st[at].lazy_add_x = 0; st[at].lazy_add_c = 0; if (l == r) { st[at].ascents_covering += add_c; } if (l < r) { if (m+1 <= r) { st[2*at+2].lazy_add_x += add_x; st[2*at+2].lazy_add_c += add_c; add_c += st[2*at+2].right_under * add_x; } if (l <= m) { st[2*at+1].lazy_add_x += add_x; st[2*at+1].lazy_add_c += add_c; } } } void add_right(int at, int l, int r, int i) { propagate(at, l, r); if (i > r || i < l) return; st[at].right_under++; if (l < r) { int m = (l+r)/2; add_right(at*2+1, l, m, i); add_right(at*2+2, m+1, r, i); } } ll count_ascents_covering(int at, int l, int r, int i) { propagate(at, l, r); if (i > r || i < l) return 0; if (l == r) { return st[at].ascents_covering; } int m = (l+r)/2; return count_ascents_covering(at*2+1, l, m, i) + count_ascents_covering(at*2+2, m+1, r, i); } int update_counts(int at, int l, int r, int i, int right_count) { propagate(at, l, r); if (r < i || l > r) { return 0; } if (l == r) { st[at].ascents_covering += right_count; } else if (i < l) { st[at].lazy_add_x++; st[at].lazy_add_c += right_count; } else { int m = (l+r)/2; right_count += update_counts(at*2+2, m+1, r, i, right_count); update_counts(at*2+1, l, m, i, right_count); } return st[at].right_under; } int main() { cin.sync_with_stdio(false); int ts; cin >> ts; vi found; rep(t,0,ts) { int n; cin >> n; vector arr(n); rep(i,0,n) { cin >> arr[i].first; arr[i].second = i; } sort(arr.rbegin(), arr.rend()); build(0, 0, n-1); ll res = 0; rep(i,0,n) { int pos = arr[i].second; ll cnt = count_ascents_covering(0, 0, n-1, pos); res += cnt; update_counts(0, 0, n-1, pos, 0); add_right(0, 0, n-1, pos); } if (res != 0) { found.push_back(t); } } cout << found.size() << endl; iter(it,found) { cout << *it+1 << endl; } return 0; }