Initially Ildar has an empty array. He performs $n$ steps. On each step he takes a subset of integers already added to the array and appends the mex of this subset to the array. 

The mex of an multiset of integers is the smallest non-negative integer not presented in the multiset. For example, the mex of the multiset $[0, 2, 3]$ is $1$, while the mex of the multiset $[1, 2, 1]$ is $0$.

More formally, on the step $m$, when Ildar already has an array $a_1, a_2, \ldots, a_{m-1}$, he chooses some subset of indices $1 \leq i_1 < i_2 < \ldots < i_k < m$ (possibly, empty), where $0 \leq k < m$, and appends the $mex(a_{i_1}, a_{i_2}, \ldots a_{i_k})$ to the end of the array.

After performing all the steps Ildar thinks that he might have made a mistake somewhere. He asks you to determine for a given array $a_1, a_2, \ldots, a_n$ the minimum step $t$ such that he has definitely made a mistake on at least one of the steps $1, 2, \ldots, t$, or determine that he could have obtained this array without mistakes.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 100\,000$) — the number of steps Ildar made.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$) — the array Ildar obtained.


-----Output-----

If Ildar could have chosen the subsets on each step in such a way that the resulting array is $a_1, a_2, \ldots, a_n$, print $-1$.

Otherwise print a single integer $t$ — the smallest index of a step such that a mistake was made on at least one step among steps $1, 2, \ldots, t$.


-----Examples-----
Input
4
0 1 2 1

Output
-1
Input
3
1 0 1

Output
1
Input
4
0 1 2 239

Output
4


-----Note-----

In the first example it is possible that Ildar made no mistakes. Here is the process he could have followed.  $1$-st step. The initial array is empty. He can choose an empty subset and obtain $0$, because the mex of an empty set is $0$. Appending this value to the end he gets the array $[0]$.  $2$-nd step. The current array is $[0]$. He can choose a subset $[0]$ and obtain an integer $1$, because $mex(0) = 1$. Appending this value to the end he gets the array $[0,1]$.  $3$-rd step. The current array is $[0,1]$. He can choose a subset $[0,1]$ and obtain an integer $2$, because $mex(0,1) = 2$. Appending this value to the end he gets the array $[0,1,2]$.  $4$-th step. The current array is $[0,1,2]$. He can choose a subset $[0]$ and obtain an integer $1$, because $mex(0) = 1$. Appending this value to the end he gets the array $[0,1,2,1]$. 

Thus, he can get the array without mistakes, so the answer is $-1$.

In the second example he has definitely made a mistake on the very first step, because he could not have obtained anything different from $0$.

In the third example he could have obtained $[0, 1, 2]$ without mistakes, but $239$ is definitely wrong.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
mx = -1
for step, elem in enumerate(a):
    if elem > mx + 1:
        print(step + 1)
        return
    else:
        mx = max(mx, elem)
print(-1)


n = int(input())
a = [int(i) for i in input().split()]
c = 0
for i in range(n):
    if a[i] > c:
        print(i+1)
        break
    else:
        c = max(a[i]+1, c)
else:
    print(-1)


n = int(input())
a = list(map(int, input().split()))

mex = -1
for i in range(n):
    if a[i] <= mex:
        continue
    elif a[i] == mex + 1:
        mex += 1
    else:
        print(i+1)
        return
print(-1)

n = int(input())
arr = list(map(int, input().split()))
arr1 = [arr[0]]
m = -1
for i, v in enumerate(arr):
    if v > m + 1:
        print(i+1)
        break
    m = max(m, v)
else:
    print(-1)



import sys
a = list(map(int, sys.stdin.readlines()[1][:-1].split()))
mx = 0
for i in range(len(a)):
	if a[i] > mx:
		print(i+1)
		return
	mx = max(mx,a[i] + 1)
print(-1)

n = int(input())
a = list(map(int, input().split()))
mx = -1
ans = -1
for i in range(n):
    if a[i] > mx+1:
        ans = i+1
        break
    else:
        mx = max(mx, a[i])
print(ans)

from math import *
#n,k=map(int,input().split())
#A = list(map(int,input().split()))
n=int(input())
A = list(map(int,input().split()))
ans =-1
maxs = 0
for j in range(n):
    if(A[j] > maxs):
        ans = j+1
        break
    else:
        maxs = max(maxs,A[j]+1)
print(ans)

n = int(input())
a = list(map(int, input().split()))
max_el = -1;
er = -1;
for i in range(len(a)):
    if a[i] - max_el > 1:
        er = i + 1;
        break
    if a[i] > max_el:
        max_el = a[i]

print(er)


n = int(input())
a = list(map(int, input().split()))
s = 0

for j, i in enumerate(a):
    if i > s:
        print(j + 1)
        return
    if i == s:
        s += 1

print(-1)


n=int(input())
#x,y,z,t1,t2,t3=map(int,input().split())
a=list(map(int,input().split()))




def qwe(a):
    f=-1
    for i in range(len(a)):
        if a[i]-f>1: return i+1
        elif a[i]-f==1: f=a[i]
    return -1


print(qwe(a))


from sys import stdin
import sys
n=int(stdin.readline().strip())
s=tuple(map(int,stdin.readline().strip().split()))
if s[0]!=0:
    print(1)
    return
x=1
ans=-1
for i in range(1,n):
    if s[i]<=x:
        x=max(x,s[i]+1)
    else:
        ans=i+1
        break
print(ans)
    


n = int(input())
mas = list(map(int, input().split()))
maxx = -1
f = 0
for i in range(n):
    if mas[i] > maxx:
        if mas[i] - 1 > maxx:
            print(i + 1)
            f = 1
            break
        else:
            maxx += 1
if f == 0:
    print(-1)

input()

m = -1

for i, a in enumerate(map(int, input().split())):
    if a > m + 1:
        print(i+1)
        break
    else:
        m = max(m, a)
else:
    print(-1)


import collections


def main():
    # # n = int(input())
    # x, y, z, t1, t2, t3 = list(map(int, input().split()))
    # stair = t1 * abs(y - x)
    # ele = t2 * (abs(y - x) + abs(z - x)) + 3 * t3
    # # print(stair, ele)
    # print("YES" if ele <= stair else "NO")

    n = int(input())
    num = list(map(int, input().split()))
    prevMax, totMax = -1, float('-inf')
    for i, v in enumerate(num):
        totMax = max(totMax, v)
        if totMax - prevMax in [0, 1]:
            prevMax = totMax
        else:
            print(i + 1)
            return
    print(-1)


main()


n = input()

A = list(map(int, input().split(" ")))

max_seen = -1

for ix, a in enumerate(A):

    if a > max_seen + 1:
        print(ix+1)
        return

    max_seen = max(max_seen, a)
print(-1)




n = int(input())
num = list(map(int, input().split()))
fl = True
used = [False] * 110000
for i in range(n):
    if num[i] == 0: 
        used[0] = True
        continue
    if num[i] > i or not used[num[i] - 1]:
        ans = i
        fl = False
        break
    else:
        used[num[i]] = True
if not fl:
    print(ans + 1)
else:
    print(-1)

#x,y,z,t1,t2,t3=list(map(int,input().split()))
s=int(input())
i=1
z=-1
for i0 in input().split():
    if int(i0)>z+1:
        print(i)
        return
    else:
        z=max(z,int(i0))
    i=i+1
print(-1)

n=int(input())
a=list(map(int,input().split()))
m=-1
for i in range(n):
    if a[i]>m+1:
        print(i+1);return
    else:
        m=max(a[i],m)
print(-1)
        
    

n=int(input())
a=list(map(int, input().split()))
maxx=-1
minn=-1
for i in range(n):
    if a[i]==maxx+1:
        maxx=a[i]
    elif a[i]>maxx+1:
        minn=i
        break
if minn==-1:
    print(minn)
else:
    print(minn+1)

n = int( input() )
a = list( map( int, input().split() ) )

i = 1
m = -1
ans = -1
for x in a:
    if x > m + 1:
        ans = i
        break
    else:
        i = i + 1
        m = max( m, x )

print( ans )


n = int(input())
A = list(map(int, input().split()))
max = -1
ans = True
ind = 1
for a in A:
  if a > max + 1:
    ans = False
    break
  if a == max + 1:
    max = a
  ind += 1
print(-1 if ans else ind)

input()
a = tuple(map(int, input().split()))
top = -1
for i, x in enumerate(a, start=1):
    if x - top <= 1:
        top = max(x, top)
    else:
        print(i)
        return
print(-1)


n=int(input())
a=list(map(int,input().split()))
m=-1
s=-1
for i in range(n):
  if(a[i]>m+1):
    s=i+1
    break
  else:
    m=max(m,a[i])
print(s)


def main():
    n = int(input())
    arr = [int(x) for x in input().strip().split()]
    s = set([-1])
    for i in range(n):
        if arr[i] - 1 not in s:
            print(i+1)
            return
        s.add(arr[i])
    
    print(-1)
    


def __starting_point():
    main()
__starting_point()

import sys

n = int(input())
l = list(map(int, input().split()))
pos_max = 0
for i in range(len(l)):
    if l[i] > pos_max:
        print(i + 1)
        return
    elif l[i] == pos_max:
            pos_max += 1
print("-1")