问题 4643 --1.珍珠项链

4643: 1.珍珠项链

题目描述

  有一串由n个珍珠组成的珍珠项链,珍珠的编号为1..n,每个珍珠都有各自的价值,我们用w[i]表示编号为i的珍珠的
价值(注意:w[i]可以小于零),已知这n个珍珠的价值量总和是n-1,现要求你在项链的某个位置断开,使得断开后的
珍珠链满足对于任意k,前k个珍珠的价值量总和不超过k-1. (对断开的一点说明, 如果在位置p断开, 那么得到的珍珠
链将一定是p,p+1,...,n,1,2,...,p-1)

输入

输入文件的第一行有一个唯一的整数n,
接下来n个用空格和换行符隔开的整数分别表示w[1],w[2],...,w[n]

输出

如果无解请输出一行"Impossible"(不含引号)否则输出一个整数表示断开后的珍珠链第一个珍珠的编号

样例输入输出

输入#1 复制
5
1 1 1 1 0
输出#1 复制
5

提示

【样例解释】
断开后的珍珠链是:5-1-2-3-4


【数据范围】
3<=n<=200,000 -1,000,000,000<=w[i]<=1,000,000,000
40%的测试数据满足n<=1,000

序号 标题 作者 发表时间 费用 订购数 操作