#include using namespace std; const int INF = 1000000000; // ================================================== // Segment Tree / Lazy Segment Tree implementation based on ACL (https://github.com/atcoder/ac-library) // ================================================== struct RangeAddRangeMinLazySegTree { int n, size, logn; vector min_value, lazy_add; RangeAddRangeMinLazySegTree() : n(0), size(1), logn(0) {} RangeAddRangeMinLazySegTree(const vector& initial_values) { init(initial_values); } void init(const vector& initial_values) { n = (int)initial_values.size(); size = 1; logn = 0; while (size < n) { size <<= 1; logn++; } min_value.assign(2 * size, INF); lazy_add.assign(size, 0); for (int i = 0; i < n; i++) { min_value[size + i] = initial_values[i]; } for (int i = size - 1; i >= 1; i--) { pull(i); } } void pull(int node) { min_value[node] = min(min_value[node * 2], min_value[node * 2 + 1]); } void apply_to_node(int node, int add_value) { min_value[node] += add_value; if (node < size) lazy_add[node] += add_value; } void push(int node) { if (lazy_add[node] != 0) { apply_to_node(node * 2, lazy_add[node]); apply_to_node(node * 2 + 1, lazy_add[node]); lazy_add[node] = 0; } } void range_add(int left, int right, int add_value) { if (left >= right) return; left += size; right += size; for (int h = logn; h >= 1; h--) { if (((left >> h) << h) != left) push(left >> h); if (((right >> h) << h) != right) push((right - 1) >> h); } int original_left = left; int original_right = right; while (left < right) { if (left & 1) apply_to_node(left++, add_value); if (right & 1) apply_to_node(--right, add_value); left >>= 1; right >>= 1; } left = original_left; right = original_right; for (int h = 1; h <= logn; h++) { if (((left >> h) << h) != left) pull(left >> h); if (((right >> h) << h) != right) pull((right - 1) >> h); } } int all_min() const { return min_value[1]; } template int max_right(int left, Predicate pred) { if (left == n) return n; left += size; for (int h = logn; h >= 1; h--) { push(left >> h); } int current_min = INF; do { while ((left & 1) == 0) left >>= 1; int next_min = min(current_min, min_value[left]); if (!pred(next_min)) { while (left < size) { push(left); left *= 2; int candidate_min = min(current_min, min_value[left]); if (pred(candidate_min)) { current_min = candidate_min; left++; } } return left - size; } current_min = next_min; left++; } while ((left & -left) != left); return n; } }; struct PointSetRangeMinSegTree { int n, size; vector min_value; PointSetRangeMinSegTree() : n(0), size(1) {} PointSetRangeMinSegTree(const vector& initial_values) { init(initial_values); } void init(const vector& initial_values) { n = (int)initial_values.size(); size = 1; while (size < n) size <<= 1; min_value.assign(2 * size, INF); for (int i = 0; i < n; i++) { min_value[size + i] = initial_values[i]; } for (int i = size - 1; i >= 1; i--) { min_value[i] = min(min_value[i * 2], min_value[i * 2 + 1]); } } void set_value(int index, int value) { index += size; min_value[index] = value; while (index >>= 1) { min_value[index] = min(min_value[index * 2], min_value[index * 2 + 1]); } } int all_min() const { return min_value[1]; } template int max_right(int left, Predicate pred) { if (left == n) return n; left += size; int current_min = INF; do { while ((left & 1) == 0) left >>= 1; int next_min = min(current_min, min_value[left]); if (!pred(next_min)) { while (left < size) { left *= 2; int candidate_min = min(current_min, min_value[left]); if (pred(candidate_min)) { current_min = candidate_min; left++; } } return left - size; } current_min = next_min; left++; } while ((left & -left) != left); return n; } }; // ================================================== // Main solution // ================================================== int main() { int N, K, M; cin >> N >> K >> M; vector A(N + 1); long long S = 0; for (int i = 1; i <= N; i++) { cin >> A[i]; S += A[i]; } if (S % (N + 1) != 0) { cout << -1 << '\n'; return 0; } long long T = S / (N + 1); if (T < 1) { cout << -1 << '\n'; return 0; } vector W(N + 1); for (int i = 1; i <= N; i++) { W[i] = A[i] - T; if (W[i] < 0) { cout << -1 << '\n'; return 0; } } if (W[M] < 1) { cout << -1 << '\n'; return 0; } if (A[M] - 2 < K) { cout << -1 << '\n'; return 0; } int m = (int)(T - 1); vector B(N + 1, 0), rem(N + 1, 0); vector deadline(N + 1, INF); vector deadline_count(max(1, m) + 1, 0); int sumB = 0; for (int i = 1; i <= N; i++) { int b = W[i] - (i == M ? 1 : 0); if (b < 0) { cout << -1 << '\n'; return 0; } B[i] = b; rem[i] = b; sumB += b; if (b > 0) { int d = K + 1 - b; if (d < 1) { cout << -1 << '\n'; return 0; } int effective_deadline = min(d, m); deadline[i] = effective_deadline; deadline_count[effective_deadline] += b; } } assert(sumB == m); if (m == 0) { cout << 1 << '\n'; cout << M << '\n'; return 0; } vector slack_init(m + 1, INF); int pref = 0; for (int x = 1; x <= m; x++) { pref += deadline_count[x]; int slack = x - pref; if (slack < 0) { cout << -1 << '\n'; return 0; } slack_init[x] = slack; } assert(pref == m); RangeAddRangeMinLazySegTree slack_tree(slack_init); vector team_init(N + 1, INF); for (int i = 1; i <= N; i++) { if (rem[i] > 0) { team_init[i] = deadline[i]; } } PointSetRangeMinSegTree team_tree(team_init); vector ans; ans.reserve((size_t)T); for (int p = 1; p <= m; p++) { if (team_tree.all_min() < p) { cout << -1 << '\n'; return 0; } int first_zero = slack_tree.max_right(p, [](int min_slack) { return min_slack > 0; }); int E = (first_zero == m + 1 ? m + 1 : first_zero); int c = team_tree.max_right(1, [&](int min_deadline) { return min_deadline > E; }); if (c == N + 1) { cout << -1 << '\n'; return 0; } ans.push_back(c); if (p < deadline[c]) { slack_tree.range_add(p, deadline[c], -1); } rem[c]--; if (rem[c] == 0) { team_tree.set_value(c, INF); } } ans.push_back(M); cout << ans.size() << '\n'; for (int i = 0; i < (int)ans.size(); i++) { if (i) cout << ' '; cout << ans[i]; } cout << '\n'; return 0; }