#include using namespace std; const int MAX_N = 400000 + 10; const int MAX_B = 40000 + 10; int v[MAX_N]; int cnt[MAX_N]; vector pos; bool inc[MAX_N]; int n; int must; int sum = 0; unsigned int DP[MAX_B][MAX_B / 32]; //DP[i][j] = can we obtain sum i from the first j elements bool get(int i, int j) { return DP[i][j / 32] & (1 << (j % 32)); } void mset(int i, int j) { DP[i][j / 32] |= 1 << (j % 32); } void brut() { mset(0, 0); int s = 0; int at = n; for(int i = 0; i < n; ++i) { for(int j = 1; j <= n; ++j) { if(!get(i, j - 1)) continue; int nxt = i + v[j]; if(nxt >= n) nxt -= n; mset(i, j); mset(nxt, j); if(nxt == 0) { at = j; break; } } } assert(get(s, at)); vector ans; while(at > 0) { int prev = s - v[at]; if(prev < 0) prev += n; if(get(prev, at - 1)) { //we got to (s, at) from (prev, at - 1) //so we included v[at] ans.push_back(at); s = prev; --at; } else { //we did not include v[at] --at; } } cout << ans.size() << "\n"; for(auto i: ans) cout << i << " "; cout << "\n"; long long sum = 0; for(auto i: ans) sum += v[i]; assert(sum % n == 0); } int main() { srand(time(0)); cin >> n; for(int i = 1; i <= n; ++i) { cin >> v[i]; v[i] = v[i] % n; if(v[i] == 0) { cout << 1 << "\n"; cout << i << "\n"; return 0; } sum += v[i]; if(sum >= n) sum -= n; inc[i] = 1; } if(n <= 40000) { brut(); return 0; } //we need to reduce sum to 0 while(sum != 0) { int x = rand() % n; if(inc[x]) { sum -= v[x]; if(sum < 0) sum += n; inc[x] = 0; } else { sum += v[x]; if(sum > 0) sum += n; inc[x] = 1; } } int cnt = 0; for(int i = 1; i <= n; ++i) cnt += inc[i]; cout << cnt << "\n"; long long total = 0; for(int i = 1; i <= n; ++i) { if(inc[i]) { cout << i << " " ; total += v[i]; } } cout << "\n"; assert(total % n == 0); return 0; }