垃圾佬的项链

TimeLimit:1000MS  MemoryLimit:128MB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description

垃圾佬有一串由n颗珍珠组成的珍珠项链,珍珠的编号为1..n,每颗珍珠都有各自的价值,我们用w[i]表示编号为i的珍珠的价值(注意:w[i]可以小于零,且均为整数),已知这n颗珍珠的价值量总和是n-1,现要求你在项链的第p处断开,使得断开后的

珍珠链满足对于任意k,前k颗珍珠的价值量总和不超过k-1. (对断开的一点说明, 如果在位置p处断开, 那么得到的珍珠项链是p,p+1,...,n,1,2,...,p-1)

Input

输入文件的第一行有一个唯一的整数n,

接下来一行有n个整数,分别表示w[1],w[2],...,w[n]

【数据范围】

3<=n<=200,000

-1,000,000,000<=w[i]<=1,000,000,000,且均为整数

Output

输出一行,包括一个整数条件的位置p,即满足条件的位置p。如果有多个p满足条件,输出最大的那个。如果无解请输出一行"Impossible"(不含引号)

SampleInput
5
1 1 1 1 0
SampleOutput
5
【对样例的解释】
断开后的珍珠链是:5-1-2-3-4
Submit
题目统计信息详细
总AC数38
通过人数30
尝试人数31
总提交量84
AC率35.71%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: