import sys # Pythonでの深い再帰の対応 sys.setrecursionlimit(300000) class LazySegTree: """区間加算と区間最小値取得、および条件を満たす最初のインデックス検索をサポートするセグメント木""" def __init__(self, data): self.n = len(data) self.size = 1 while self.size < self.n: self.size *= 2 self.tree = [float('inf')] * (2 * self.size) self.lazy = [0] * (2 * self.size) for i in range(self.n): self.tree[self.size - 1 + i] = data[i] for i in range(self.size - 2, -1, -1): self.tree[i] = min(self.tree[2 * i + 1], self.tree[2 * i + 2]) def _eval(self, k, l, r): if self.lazy[k] != 0: self.tree[k] += self.lazy[k] if r - l > 1: self.lazy[2 * k + 1] += self.lazy[k] self.lazy[2 * k + 2] += self.lazy[k] self.lazy[k] = 0 def add(self, a, b, x): self._add(a, b, x, 0, 0, self.size) def _add(self, a, b, x, k, l, r): self._eval(k, l, r) if a <= l and r <= b: self.lazy[k] += x self._eval(k, l, r) elif a < r and l < b: mid = (l + r) // 2 self._add(a, b, x, 2 * k + 1, l, mid) self._add(a, b, x, 2 * k + 2, mid, r) self.tree[k] = min(self.tree[2 * k + 1], self.tree[2 * k + 2]) def find_first(self, a, b, x): """区間 [a, b) の中で値が x 以下となる最初のインデックスを返す""" return self._find_first(a, b, x, 0, 0, self.size) def _find_first(self, a, b, x, k, l, r): self._eval(k, l, r) if b <= l or r <= a or self.tree[k] > x: return -1 if r - l == 1: return l mid = (l + r) // 2 res = self._find_first(a, b, x, 2 * k + 1, l, mid) if res != -1: return res return self._find_first(a, b, x, 2 * k + 2, mid, r) class PointSegTree: """点更新と区間最小値取得を非再帰で行うセグメント木 (チーム選択用)""" def __init__(self, n): self.size = 1 while self.size < n: self.size *= 2 self.tree = [(float('inf'), -1)] * (2 * self.size) def update(self, i, val): i += self.size - 1 self.tree[i] = val while i > 0: i = (i - 1) // 2 self.tree[i] = min(self.tree[2 * i + 1], self.tree[2 * i + 2]) def get_min(self, a, b): res = (float('inf'), -1) l = a + self.size - 1 r = b + self.size - 1 while l < r: if not (l & 1): # l が親の右側の子 if self.tree[l][0] < res[0]: res = self.tree[l] l += 1 if not (r & 1): # r が親の右側の子 r -= 1 if self.tree[r][0] < res[0]: res = self.tree[r] l = (l - 1) // 2 r = (r - 1) // 2 return res def main(): input_data = sys.stdin.read().split() if not input_data: return N = int(input_data[0]) K = int(input_data[1]) M = int(input_data[2]) A = [int(x) for x in input_data[3:3+N]] total_A = sum(A) # 合計スコアが1試合ごとの加算量(N+1)で割り切れない場合は矛盾 if total_A % (N + 1) != 0: print("-1") return T = total_A // (N + 1) if T == 0: print("-1") return W = [a - T for a in A] for w in W: if w < 0: print("-1") return # Mチームは最低でも1回(最後の試合)勝ち、最終的にスコアが(K+2)以上でなければならない if W[M - 1] < 1 or A[M - 1] < K + 2: print("-1") return # 1試合のみの場合は条件が揃っているかだけですでに確定 if T == 1: print(1) print(M) return V = [0] * N D = [0] * N for i in range(N): if i == M - 1: V[i] = W[i] - 1 D[i] = K - W[i] + 2 else: V[i] = W[i] D[i] = K - W[i] + 1 if V[i] > 0 and D[i] <= 0: print("-1") return # 全てのスロットは最大でもT-1までしかスケジュールできない D_prime = [0] * N for i in range(N): if V[i] > 0: D_prime[i] = min(T - 1, D[i]) C = [0] * T for i in range(N): if V[i] > 0: C[D_prime[i]] += V[i] # 初期の猶予(E_init)を計算 E_init = [0] * T S_val = 0 for k in range(1, T): S_val += C[k] E_init[k] = k - S_val # 猶予がマイナスになる場合は最初からスケジュール不能 if E_init[k] < 0: print("-1") return # チームを期限別に割り当て teams = [[] for _ in range(T)] for i in range(N): if V[i] > 0: for _ in range(V[i]): teams[D_prime[i]].append(i + 1) for d in range(1, T): teams[d].sort(reverse=True) # チーム探索用のセグメント木初期化 team_seg = PointSegTree(T) for d in range(1, T): if teams[d]: team_seg.update(d, (teams[d][-1], d)) else: team_seg.update(d, (float('inf'), d)) e_seg = LazySegTree(E_init) ans = [] # 各スロット t = 1, 2, ..., T-1 について前から順に貪欲に決定 for t in range(1, T): # 条件を破らないギリギリの期限(xcrit)を特定 xcrit = e_seg.find_first(t, T, t - 1) if xcrit == -1: xcrit = T - 1 # 猶予の中で辞書順最小のチームを選択 min_team, d_opt = team_seg.get_min(t, xcrit + 1) if min_team == float('inf'): print("-1") return ans.append(min_team) teams[d_opt].pop() # 抽出元の期限リストを更新 if teams[d_opt]: team_seg.update(d_opt, (teams[d_opt][-1], d_opt)) else: team_seg.update(d_opt, (float('inf'), d_opt)) # 選択したチームの期限以後の猶予を回復させる e_seg.add(d_opt, T, 1) # 最後に優勝チームを追加して出力 ans.append(M) print(T) print(" ".join(map(str, ans))) if __name__ == '__main__': main()