#include #include #include #include #include #include #include using namespace std; // Find existence of 213 relative permutation in n lg n time. bool solve(){ int n; cin >> n; deque> xy(n), yx(n); // map one coord to the other coord for(int x = 0; x < n; ++x){ int y; cin >> y; xy[x] = {x, y}; yx[x] = {y, x}; } sort(begin(xy), end(xy)); sort(begin(yx), end(yx)); // Repeatedly drop points: // - bottom left // - top left // - bottom right while(!xy.empty()){ if(xy.front().second == yx.front().first){ xy.pop_front(); yx.pop_front(); continue; } if(xy.front().second == yx.back().first){ xy.pop_front(); yx.pop_back(); continue; } if(xy.back().second == yx.front().first){ xy.pop_back(); yx.pop_front(); continue; } break; } // Get top right front. stack> s; s.push({-1, 2'000'000'000}); for(int i = 0; i < xy.size(); ++i){ while(xy[i].second >= s.top().second) s.pop(); s.push(xy[i]); } // For each top right point, try to find a descending pair left below it. for(auto [x, y] : xy){ if(x<0) continue; int top = -1; for(auto [x2, y2] : xy){ if(y2 == y) break; if(y2 > y) continue; if(y2 < top) return true; top = y2; } } return false; } int main(){ int ts; cin >> ts; vector ans; for(int t = 1; t <= ts; ++t) if(solve()) ans.push_back(t); cout << ans.size() << endl; for(auto x : ans) cout << x << endl; }