The Central Company has an office with a sophisticated security system. There are $10^6$ employees, numbered from $1$ to $10^6$.

The security system logs entrances and departures. The entrance of the $i$-th employee is denoted by the integer $i$, while the departure of the $i$-th employee is denoted by the integer $-i$.

The company has some strict rules about access to its office:

  An employee can enter the office at most once per day.  He obviously can't leave the office if he didn't enter it earlier that day.  In the beginning and at the end of every day, the office is empty (employees can't stay at night). It may also be empty at any moment of the day. 

Any array of events satisfying these conditions is called a valid day.

Some examples of valid or invalid days:

  $[1, 7, -7, 3, -1, -3]$ is a valid day ($1$ enters, $7$ enters, $7$ leaves, $3$ enters, $1$ leaves, $3$ leaves).  $[2, -2, 3, -3]$ is also a valid day.  $[2, 5, -5, 5, -5, -2]$ is not a valid day, because $5$ entered the office twice during the same day.  $[-4, 4]$ is not a valid day, because $4$ left the office without being in it.  $[4]$ is not a valid day, because $4$ entered the office and didn't leave it before the end of the day. 

There are $n$ events $a_1, a_2, \ldots, a_n$, in the order they occurred. This array corresponds to one or more consecutive days. The system administrator erased the dates of events by mistake, but he didn't change the order of the events.

You must partition (to cut) the array $a$ of events into contiguous subarrays, which must represent non-empty valid days (or say that it's impossible). Each array element should belong to exactly one contiguous subarray of a partition. Each contiguous subarray of a partition should be a valid day.

For example, if $n=8$ and $a=[1, -1, 1, 2, -1, -2, 3, -3]$ then he can partition it into two contiguous subarrays which are valid days: $a = [1, -1~ \boldsymbol{|}~ 1, 2, -1, -2, 3, -3]$.

Help the administrator to partition the given array $a$ in the required way or report that it is impossible to do. Find any required partition, you should not minimize or maximize the number of parts.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^6 \le a_i \le 10^6$ and $a_i \neq 0$).


-----Output-----

If there is no valid partition, print $-1$. Otherwise, print any valid partition in the following format:

  On the first line print the number $d$ of days ($1 \le d \le n$).  On the second line, print $d$ integers $c_1, c_2, \ldots, c_d$ ($1 \le c_i \le n$ and $c_1 + c_2 + \ldots + c_d = n$), where $c_i$ is the number of events in the $i$-th day. 

If there are many valid solutions, you can print any of them. You don't have to minimize nor maximize the number of days.


-----Examples-----
Input
6
1 7 -7 3 -1 -3

Output
1
6

Input
8
1 -1 1 2 -1 -2 3 -3

Output
2
2 6

Input
6
2 5 -5 5 -5 -2

Output
-1

Input
3
-8 1 1

Output
-1



-----Note-----

In the first example, the whole array is a valid day.

In the second example, one possible valid solution is to split the array into $[1, -1]$ and $[1, 2, -1, -2, 3, -3]$ ($d = 2$ and $c = [2, 6]$). The only other valid solution would be to split the array into $[1, -1]$, $[1, 2, -1, -2]$ and $[3, -3]$ ($d = 3$ and $c = [2, 4, 2]$). Both solutions are accepted.

In the third and fourth examples, we can prove that there exists no valid solution. Please note that the array given in input is not guaranteed to represent a coherent set of events.

Difficulty: interview

Starter code:

Solutions:
import sys
from collections import Counter
readline = sys.stdin.readline

N = int(readline())
A = list(map(int, readline().split()))

S = set()

ans = True
Ans = [] 
cnt = 0
for a in A:
    cnt += 1
    if a > 0:
        S.add(a)
    else:
        a = -a
        if a not in S:
            ans = False
            break
        S.remove(a)
    if not S:
        Ans.append(cnt)
        cnt = 0

if cnt:
    ans = False

if ans:
    A.reverse()
    for c in Ans:
        CA = Counter()
        for _ in range(c):
            CA[abs(A.pop())] += 1
        if any(v > 2 for v in CA.values()):
            ans = False
            break

if ans:
    print(len(Ans))
    print(*Ans)
else:
    print(-1)

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

office = set()
ans=[]
curc=1
curday = []
for i in range(n):
    if a[i] < 0:
        if -1*a[i] not in office:
            print("-1")
            quit()
        else:
            office.remove(-1*a[i])
            if len(office) == 0:
                ans.append(curc)
                curc=0
                curday=[]
    else:
        if a[i] in office:
            print(-1)
            quit()
        else:
            if a[i] in curday:
                print(-1)
                quit()
            office.add(a[i])
            curday.append(a[i])
    curc += 1

if len(office) != 0:
    print("-1")
    quit()

print(str(len(ans)))
print(" ".join(str(k) for k in ans))

n = int(input())

work = set()
day = set()

prei = 0
ans = []

for i, x in enumerate(map(int, input().split())):
	if x > 0:
		if x in work:
			print(-1)
			break

		if x in day:
			print(-1)
			break

		day.add(x)
		work.add(x)

	if x < 0:
		if -x not in work:
			print(-1)
			break

		work.remove(-x)

		if len(work) == 0:
			ans.append(i - prei + 1)
			prei = i + 1
			day = set()

else:
	if prei != n:
		print(-1)

	else:

		print(len(ans))
		print(*ans)

n = int(input())
a = list(map(int, input().split()))
ans, q1, naw, q2 = [], -1, {}, 0
for q in range(len(a)):
    if a[q] < 0 and -a[q] not in naw:
        print(-1)
        break
    elif a[q] < 0:
        naw[-a[q]] -= 1
        q2 -= 1
        if naw[-a[q]] < 0:
            print(-1)
            break
    elif a[q] in naw:
        print(-1)
        break
    else:
        naw[a[q]] = 1
        q2 += 1
    if q2 == 0:
        naw = {}
        ans.append(q-q1)
        q1 = q
else:
    if q2 == 0:
        print(len(ans))
        print(*ans)
    else:
        print(-1)


from collections import defaultdict
n = int(input())
l = [*map(int, input().split())]

valid = True
res = []

cnt = defaultdict(int)
cur = 0
for e in l:
    if e < 0:
        valid &= cnt[-e] == 1
        cnt[-e] += 1
        cur += 1
    else:
        valid &= cnt[e] == 0
        cnt[e] += 1
    if cur == len(cnt):
        res.append(2 * cur)
        cnt.clear()
        cur = 0

    if not valid: break
valid &= cur == 0 and not cnt
if not valid:
    print(-1)
else:
    print(len(res))
    print(*res)

import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int,minp().split()))

def solve():
	n = mint()
	s = set()
	w = set()
	k = 0
	r = []
	for i in mints():
		k += 1
		if i < 0:
			if (-i) not in s:
				print(-1)
				return
			s.remove(-i)
			if len(s) == 0:
				r.append(k)
				k = 0
				w = set()
		else:
			if i in w:
				print(-1)
				return
			s.add(i)
			w.add(i)
	if len(s) != 0:
		print(-1)
		return
	print(len(r))
	print(' '.join(map(str,r)))

solve()


n = int(input())
soot = set()
usoot = set()
a = list(map(int,input().split()))
ans = []
f = True
c = 0
for i in a:
    c += 1
    if i < 0:
        if -i in soot:
            soot.remove(-i)
            usoot.add(-i)
        else:
            f = False
            break
    else:
        if i in soot or i in usoot:
            f = False
            break
        else:
            soot.add(i)
    if len(soot) == 0:
        usoot = set()
        ans.append(c)
        c = 0
if len(soot) != 0:
        f = False
if f:
    print(len(ans))
    for i in ans:
        print(i, end = " ")
else:
    print(-1)
        


3

import os
import sys


def main():
    N = read_int()
    A = read_ints()
    ans = solve(N, A)
    if not ans:
        print('-1')
    else:
        print(len(ans))
        print(*ans)


def solve(N, A):
    ans = []

    start = 0
    present = set()
    left = set()
    for i, a in enumerate(A):
        if a > 0:
            if a in present or a in left:
                return None
            present.add(a)
        else:
            a = -a
            if a not in present:
                return None
            present.remove(a)
            left.add(a)

            if not present:
                ans.append(i - start + 1)
                start = i + 1
                left = set()

    if start != N:
        return None
    return ans


###############################################################################
# AUXILIARY FUNCTIONS

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def __starting_point():
    main()

__starting_point()

input()
ans = []
cur = 0
status = set()
were = set()
try:
    for ai in map(int, input().split()):
        cur += 1
        if ai < 0:
            status.remove(abs(ai))
            if not status:
                ans.append(cur)
                cur = 0
                were = set()
        else:
            assert ai not in were
            status.add(ai)
            were.add(ai)
    assert not were
    print(len(ans))
    print(*ans)
except (AssertionError, KeyError):
    print('-1')


n=int(input())
t=[int(s) for s in input().split()]
la=set()
pl=set()
bon=True
las=0
rep=[]
for i in range(n):
    e=abs(t[i])
    if t[i]>0:
        if e in la or e in pl:
            bon=False
            break
        else:
            la.add(e)
    else:
        if e in la:
            la.remove(e)
            pl.add(e)
            if len(la)==0:
                la=set()
                pl=set()
                rep.append(i+1-las)
                las=i+1
        else:
            bon=False
            break
if len(la)==0 and len(pl)==0 and bon:
    print(len(rep))
    for i in rep:
        print(i)
else:
    print(-1)

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

def work():
    c, d = set(), set()
    r = [0]
    for x in a:
        r[-1] += 1
        if x > 0:
            if x in c:
                return 0
            if x in d:
                return 0
            c.add(x)
            d.add(x)
        if x < 0:
            if -x not in c:
                return 0
            c.remove(-x)
            if not c:
                r.append(0)
                d = set()
    return 0 if r[-1] else r[:-1]

ans = work()
if ans:
    print(len(ans))
    print(*ans)
else:
    print(-1)

import math
from decimal import Decimal
import heapq
from collections import deque
def na():
	n = int(input())
	b = [int(x) for x in input().split()]
	return n,b
 
 
def nab():
	n = int(input())
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	return n,b,c
 
 
def dv():
	n, m = list(map(int, input().split()))
	return n,m
 
 
def dva():
	n, m = list(map(int, input().split()))
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	return n,m,b
 
 
def eratosthenes(n): 
	sieve = list(range(n + 1))
	for i in sieve:
		if i > 1:
			for j in range(i + i, len(sieve), i):
				sieve[j] = 0
	return sorted(set(sieve))
 
 
def lol(lst,k):
	k=k%len(lst)
	ret=[0]*len(lst)
	for i in range(len(lst)):
		if i+k<len(lst) and i+k>=0:
			ret[i]=lst[i+k]
		if i+k>=len(lst):
			ret[i]=lst[i+k-len(lst)]
		if i+k<0:
			ret[i]=lst[i+k+len(lst)]
	return(ret)
def nm():
	n = int(input())
	b = [int(x) for x in input().split()]
	m = int(input())
	c = [int(x) for x in input().split()]
	return n,b,m,c
 
 
def dvs():
	n = int(input())
	m = int(input())
	return n, m 
 
def fact(a, b):
	c = []
	ans = 0
	f = int(math.sqrt(a))
	for i in range(1, f + 1):
		if a % i == 0:
			c.append(i)
	l = len(c)
	for i in range(l):
		c.append(a // c[i])
	for i in range(len(c)):
		if c[i] <= b:
			ans += 1
	if a / f == f and b >= f:
		return ans - 1
	return ans
 

n = int(input())
a = list(map(int, input().split()))
ans = []
s = set([a[0]])
used = set()
lst = 0
for q in range(1, n):
	i = a[q]
	if i < 0:
		d = i * (-1)
		if d not in s:
			print(-1)
			return
		else:
			s -= set([d])
		if len(s) == 0:
			ans.append(q + 1 - lst)
			used = set()
			lst = q + 1
	else:
		if i in s or i in used:
			print(-1)
			return
		else:
			used.add(i)
			s.add(i)
if len(s) != 0:
	print(-1)
	return
print(len(ans))
print(*ans)


import sys
input = sys.stdin.readline

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

NOW=set()
USED=set()
ANS=[0]
for i in range(n):
    if A[i]>0:
        if A[i] in NOW or A[i] in USED:
            print(-1)
            return
        else:
            NOW.add(A[i])
            USED.add(A[i])

    else:
        if -A[i] in NOW:
            NOW.remove(-A[i])
        else:
            print(-1)
            return
    if NOW==set():
        ANS.append(i+1)
        USED=set()

if len(NOW)>0:
    print(-1)
    return

print(len(ANS)-1)
ANS2=[ANS[i]-ANS[i-1] for i in range(1,len(ANS))]
print(" ".join(map(str,ANS2)))


import sys
input = sys.stdin.readline


n = int(input())
a = list(map(int, input().split()))
set_ = set([]) 
set_2 = set([])
ans = []


for i in range(n):
    if a[i] > 0:
        if a[i] not in set_2:
            set_.add(a[i])
        else:
            print(-1)
            return
        set_2.add(a[i])
    else:
        if abs(a[i]) in set_:
            set_.remove(-a[i])
        else:
            print(-1)
            return

    if not set_:
        set_2 = set([])
        ans.append(i+1)

if set_:
    print(-1)
    return
    
res = [0]*len(ans)
for i in range(len(ans)):
    if i == 0:
        res[i] = ans[i]
    else:
        res[i] = ans[i] - ans[i-1]
print(len(res))
print(*res)

N = int(input())
A = list(map(int, input().split()))
Q = []
L = [0] * (10**6+1)
Ans = []
cnt = 0
cnt_emp = 0
for a in A:
    cnt += 1
    if a>0:
        Q.append(a)
        l = L[a]
        if l==0:
            L[a] = 1
            cnt_emp += 1
        elif l==1:
            print(-1)
            return
        else:
            print(-1)
            return
    else:
        a = -a
        l = L[a]
        if l==0:
            print(-1)
            return
        elif l==1:
            L[a] = 2
            cnt_emp -= 1
            if cnt_emp==0:
                Ans.append(cnt)
                cnt = 0
                for q in Q:
                    L[q] = 0
                Q = []
        else:
            print(-1)
            return
if cnt_emp!=0:
    print(-1)
    return
print(len(Ans))
print(" ".join(map(str, Ans)))


#600_B

n = int(input())

ln = [int(i) for i in input().split(" ")]

seen = {}
sm = 0

f = True

tk = 0

pts = []

for i in range(0, len(ln)):
    sm += ln[i]
    if ln[i] < 0 and -ln[i] not in seen:
        f = False
    if ln[i] in seen:
        seen[ln[i]] += 1
        f = False
        break
    else:
        seen[ln[i]] = 1
    tk += 1
    if sm == 0:
        seen = {}
        pts.append(tk)
        tk = 0
if sm != 0:
    f = False

if not f:
    print(-1)
else:
    print(len(pts))
    print(" ".join([str(i) for i in pts]))


from sys import stdin
n=int(stdin.readline().strip())
s=list(map(int,stdin.readline().strip().split()))
en=[0 for i in range(10**6+7)]
vis=[0 for i in range(10**6+7)]
ans=[0]
flag=True
cnt=0
v=[]
for i in range(n):
    ans[-1]+=1
    vis
    if s[i]>0:
        en[s[i]]+=1
        vis[s[i]]+=1
        v.append(s[i])
        cnt+=1
    else:
        en[-s[i]]-=1
        cnt-=1
    s[i]=abs(s[i])
    if en[s[i]]<0 or en[s[i]]>1 or vis[s[i]]>1:
        flag=False
        break
    
    if i>0 and cnt==0:
        ans.append(0)
        for j in v:
            vis[j]=0
        v=[]
    
if flag==False or ans[-1]!=0:
    print(-1)
else:
    if ans[-1]==0:
        ans.pop()
    print(len(ans))
    print(*ans)


n = int(input())

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

days = [] #when days end
ok = True

tod = set()
now = set()



for i in range(n):
    #print(i, tod, now)
    if (a[i]>0):
        if (a[i] in tod):
            ok = False
            break
        else:
            tod.add(a[i])
            now.add(a[i])
    else:
        if not (-a[i] in now):
            ok = False
            break
        else:
            now.discard(-a[i])
    if (len(now)==0):
        days.append(i+1)
        tod = set()
        now = set()

if (len(now)!=0):
    ok = False

if (ok):
    print(len(days))
    days = [0]+days
    for i in range(1, len(days)):
        print(days[i]-days[i-1], end=' ')
else:
    print(-1)

n = int(input())
A = input().split()
A = [int(k) for k in A]

imposs = False
days = []
curr_empl = set()
day_empl = set()
d_s = 0
for i in range(n):
    #print(curr_empl)
    #print(day_empl)
    e = A[i]
    if e < 0:
        if -e not in curr_empl:
            imposs = True
            break
        curr_empl.remove(-e)
    else:
        if e in day_empl:
            imposs = True
            break
        day_empl.add(e)
        curr_empl.add(e)
    if len(curr_empl) == 0:
        curr_empl = set()
        day_empl = set()
        days.append(i - d_s + 1)
        d_s = i + 1

if imposs or len(curr_empl) > 0:
    print(-1)
else:
    print(len(days))
    print(' '.join([str(di) for di in days]))



import sys
import collections
from collections import Counter
import itertools
import math
import timeit

#input = sys.stdin.readline

#########################
# imgur.com/Pkt7iIf.png #
#########################

def sieve(n):
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r

def divs(n, start=1):
    divisors = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if n % i == 0:
            if n / i == i:
                divisors.append(i)
            else:
                divisors.extend([i, n // i])
    return divisors

def divn(n, primes):
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t

def flin(d, x, default = -1):
    left = right = -1
    for i in range(len(d)):
        if d[i] == x:
            if left == -1: left = i
            right = i
    if left == -1:
        return (default, default)
    else:
        return (left, right)

def ceil(n, k): return n // k + (n % k != 0)
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(map(int, input().split()))
def lcm(a, b): return abs(a * b) // math.gcd(a, b)
def prr(a, sep=' '): print(sep.join(map(str, a)))
def dd(): return collections.defaultdict(int)
def ddl(): return collections.defaultdict(list)

n = ii()
d = li()

sin = set()
res = []
prev = -1
flag = dd()
for i in range(n):
    if d[i] > 0 and d[i] not in sin and flag[d[i]] == 0:
        sin.add(d[i])
        flag[d[i]] = 1
    elif d[i] < 0 and -d[i] in sin:
        sin.remove(-d[i])
    else:
        print(-1);return()

    if len(sin) == 0:
        res.append(i - prev)
        prev = i
        flag = dd()

if len(sin) != 0:
    print(-1);return()
print(len(res))
prr(res, sep = ' ')





import sys
n = int(sys.stdin.readline())
employees = list(map(int, sys.stdin.readline().split(" ")))
days = []
curr = 0
count = 0
inside = set()
seenToday = set()
while curr < n:
    count += 1
    employee = employees[curr]
    if employee > 0:
        if employee in seenToday:
            days = []
            break
        inside.add(employee)
        seenToday.add(employee)
    else:
        if abs(employee) not in inside:
            days = []
            break
        inside.remove(abs(employee))
        if len(inside) == 0:
            days.append(count)
            count = 0
            seenToday = set()
    curr += 1

if len(days) == 0 or len(inside) > 0:
    print(-1)
else:
    print(len(days))
    for n in days:
        print(n, end = " ")

import sys
import math
from collections import defaultdict
from collections import deque
from itertools import combinations
from itertools import permutations
input = lambda : sys.stdin.readline().rstrip()
read = lambda : map(int, input().split())
def write(*args, sep="\n"):
  for i in args:
    sys.stdout.write("{}{}".format(i, sep))
INF = float('inf')
MOD = int(1e9 + 7)

n = int(input())
arr = list(read())
dp = [arr[0]]
flag = True 

for i in range(1, n):
  dp.append(dp[-1] + arr[i])

if len(list(filter(lambda x : x < 0, dp))) >= 1 or dp[-1] != 0:
  print("-1")
  return

prev = -1 
can = []
for i in range(n):
  if dp[i] == 0:
    can.append((prev + 1, i))
    prev = i 

for l, r in can:
  d = defaultdict(bool)
  for i in range(l, r+1):
    if arr[i] in d:
      print("-1")
      return
    if arr[i] < 0 and not -arr[i] in d:
      print("-1")
      return
    d[arr[i]] = True 

print(len(can))
for i, j in can:
  print(j - i + 1, end = " ")
    


ints = lambda: [int(x) for x in input().split()]

def solve(arr):
    p, inside, entered = [], set(), set()
    for x in arr:
        if (x<0 and -x not in inside) or (x>0 and x in entered):
            return []
        elif x<0:
            inside.remove(-x)
            if len(inside)==0:
                p.append(2*len(entered))
                entered = set()
        else:
            inside.add(x)
            entered.add(x)
    if inside: return []
    return p

def main():
    while 1:
        try: n, = ints()
        except EOFError: break
        ans = solve(ints())
        if not ans: print('-1')
        else: print(len(ans)) ; print(*ans)
    return

main()


n=int(input())
a=list(map(int,input().split()))
s=set()
d=0
ans=[]
c=0
o=set()
for i in range(n):
	x=a[i]
	if x>0:
		if i==0:
			c+=1
			s.add(x)
			o.add(x)
		else:
			if len(s):
				if x in s or x in o:
					d=-1
					break
				else:
					c+=1
					s.add(x)
					o.add(x)
			else:
				d+=1
				ans.append(c)
				s.add(x)
				o={x}
				c=1
	elif x<0:
		if i==0:
			d=-1
			break
		else:
			if len(s):
				if -1*x in s:
					s.remove(-1*x)
					c+=1
				else:
					d=-1
					break
			else:
				d=-1
				break
if d!=-1:
	if len(s):
		print("-1")
	else:
		d+=1
		ans.append(c)
		print(d)
		print(*ans)
else:
	print("-1")

n = int(input())
a = list([int(x) for x in input().split()])
c = []
s = 0
enter = [False] * 1000001
left = [False] * 1000001
today = []

for ai in a:
    if ai > 0 and (enter[ai] or left[ai]):
        c = []
        break

    if ai < 0 and (not enter[-ai] or left[-ai]):
        c = []
        break
    
    s += ai
    if ai > 0:
        enter[ai] = True
        today.append(ai)
    else:
        left[-ai] = True
        enter[-ai] = False
        if s == 0:
            c.append((len(today)))
            for x in today:
                enter[x] = False
                left[x] = False
            today = []
    
    # print(s)

if len(c) > 0 and s == 0:
    print(str(len(c)))
    print(' '.join(str(x*2) for x in c))
else:
    print(-1)