#2370. 「BalticOI 2008」选举

内存限制:32 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: HeRaNO

题目描述

题目译自 BalticOI 2008 Day2「Elections

Byteland 国的居民最近一直为议会选举投票。现在,当结果公布的时候,党派不得不决定联合组建政府。 每个党派都会获得议会中的一定席位。这个联合政府一定是这些党派的子集,以至于联合政府在议会中的席位数严格大于半数。对于联合政府来说,席位越多越好,这是为了确保联合政府在一小部分成员缺席国会会议的情况下仍能通过他们提案的法律。
一个“过剩”的联合政府是指联合政府中的一个党派被移出后,这个剩余的联合政府在国会中仍有过半数的席位。当然,像这样可被移出的党派事实上没有权利——因为其他的联合政府成员党派可以无视这个党派的意见而强制实行法律。

任务

写一个程序能够:

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

输入格式

标准输出的第一行包含一个整数 n ,表示参加选举的党派数。党派被从 1 n 编号。
第二行包含 n 个非负整数 a_1,\cdots ,a_n ,被一个空格隔开, a_i 是第 i 个党派获得的席位数。你可以假设国会中的中的总席位数为小于等于 10^5 的正整数。

输出格式

标准输出第一行应该包含一个整数 k ,表示无过剩且在议会中有着最大可能席位数的联合政府中含有的党派数。
第二行应该包含 k 个被单个空格隔开的不同整数,表示组成联合政府的党派编号。
如果有不止一个联合政府可以满足要求,你可以输出任意一个。党派的编号可以以任意顺序输出。

样例

样例输入

4
1 3 2 4

样例输出

2
2 4

数据范围与提示

对于 40\% 的数据, n\le 20
对于全部数据, 1\le n\le 300