Stop at the First Negative Number

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given $n$ integers $a_1,\ldots,a_n$, find the first 1-based position whose value is negative. Print -1 if there is none, including $n=0$. This exercise practices exiting a loop with break.

Input

The first value is $n$, followed by exactly $n$ integers separated by whitespace. Every $a_i\in[-10^6,10^6]$.

Output

Print the first negative position, or -1.

Subtasks

• Subtask 1 (20%): $0\le n\le 8$; $-10^6\le a_i\le10^6$.

• Subtask 2 (30%): $0\le n\le 1000$; $-10^6\le a_i\le10^6$.

• Subtask 3 (50%): $0\le n\le 100000$; $-10^6\le a_i\le10^6$.

Examples

Example 1

Input:

5
2 0 -4 -7 9

Output:

3

Explanation:

Scan left to right; the first negative value determines the reported position.

Example 2

Input:

0

Output:

-1

Explanation:

Scan left to right; the first negative value determines the reported position.