#P4664. [BalticOI 2008] 选举 (Day2)

[BalticOI 2008] 选举 (Day2)

题目描述

Byteland 国的居民最近一直为议会选举投票。现在,当结果公布的时候,党派不得不决定联合组建政党。

每个党派都会获得议会中的一定席位。联合政党由这些党派中的一部分组成,他们在议会中的席位数之和严格大于总席位数的一半。对于联合政党来说,席位越多越好。

一个过剩的联合政党是指联合政党中的一个党派被移出后,剩余的政党在国会中仍有过半数的席位。

任务

请写一个程序能够:

  • 读取选举结果;
  • 找到一个在议会中有着最大可能席位数不过剩的联合政党;
  • 输出这个联合政党的描述。

输入格式

标准输入的第一行包含一个整数 nn,表示参加选举的党派数。党派被从 11nn 编号。

第二行包含 nn 个非负整数 a1,,ana_1,\dots,a_n,被一个空格隔开,第 ii 个整数 aia_i 是第 ii 个党派获得的席位数。你可以假设国会中的中的总席位数为小于等于 10510^5 的正整数。

输出格式

标准输出的第一行应该包含一个整数 kk,表示无过剩且在议会中有着最大可能席位数的联合政党中含有的党派数。

第二行应该包含 kk 个被单个空格隔开的不同整数,表示组成联合政党的党派编号。

如果有不止一个联合政党可以满足要求,你可以输出任意一个。党派的编号可以以任意顺序输出。

4
1 3 2 4
2
2 4

提示

对于 40%40\% 的数据,n20n\le 20

对于全部数据,1n3001\le n\le 300