Accumulate Until Target

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given a positive integer target $T$ and nonnegative integer contributions, start with total zero and receive contributions in order. Find the fewest reads required for the total to reach or exceed $T$. A zero contribution still counts as a read but does not increase the total.

Input

The first integer is $T$; nonnegative contributions follow. The final contribution is the first to bring the running total to or above $T$, and no additional input follows.

Output

Print the minimum number of contributions read to reach the target.

Subtasks

• Subtask 1 (20%): $1\le T\le100$, at most $5$ contributions in $[0,100]$.
• Subtask 2 (30%): $1\le T\le10^6$, at most $100$ contributions in $[0,10^6]$.
• Subtask 3 (50%): $1\le T\le10^{12}$, at most $100000$ contributions in $[0,10^9]$.

Examples

Example 1

Input

10
0 4 0 6

Output

4

Explanation

Running totals are 0, 4, 4, 10. Zeros count as reads. The target is first reached at read four.

Example 2

Input

3
3

Output

1

Explanation

The first contribution reaches the target exactly, so output one.