题目描述

从 A 城到 B 城的路程一共有 $s$ 公里。刘老师 一天可以走 $x$ 公里路，他想要从 A 城出发，在 $n$ 天内到达 B 城。

他找到了接下来 $n$ 天的天气预报，第 $i$ 天有一个天气情况 $v_i$：

• 如果 $v_i=0$，则表示第 $i$ 天是晴天，他可以正常地走 $x$ 公里；
• 如果 $v_i=-1$，则表示第 $i$ 天是雨天，他没法出门，也没法赶路；
• 如果 $v_i\ge1$，则表示第 $i$ 天的风速为 $v_i$，他受逆风影响，一天可以走 $x-v_i$ 公里。

如果对于所有 $j<i$，前 $j$ 天他能走的总路程都不足 $s$ 公里，而前 $i$ 天他能走的总路程不少于 $s$ 公里，那么他可以在第 $i$ 天到达 B 城。他想知道他会在第几天到达。

输入格式

第一行输入三个整数表示 $n,s,x$。

第二行输入 $n$ 个整数，第 $i$ 个表示 $v_i$。

输出格式

输出一行一个整数表示 刘老师 会在第几天到达 B 城。如果他在 $n$ 天内无法到达，则输出 $-1$。

3 5 3
0 -1 1

3

3 4 2
0 -1 1

-1

提示

样例解释

对于第一组样例，刘老师 第一天能走 $3$ 公里，第二天无法赶路，第三天先后退 $1$ 公里后再走 $3$ 公里。前两天他总共只能走 $3$ 公里，但前三天他总共能走 $3+(3-1)=5$ 公里，因此他能在第三天到达 B 城。

对于第二组样例，刘老师 前两天总共只能走 $2$ 公里，前三天总共只能走 $2+(2-1)=3$ 公里，因此他在 $n$ 天内无法到达 B 城。

数据范围与限制

对于 $20\%$ 的数据，保证 $v_i=0$；

对于 $60\%$ 的数据，保证 $v_i\le0$；

对于所有数据，保证 $1\le n\le10^6$，$1\le s,x\le 10^9$，$-1\le v_i\le x$。