Polycarpus is the director of a large corporation. There are n secretaries working for the corporation, each of them corresponds via the famous Spyke VoIP system during the day. We know that when two people call each other via Spyke, the Spyke network assigns a unique ID to this call, a positive integer session number.

One day Polycarpus wondered which secretaries are talking via the Spyke and which are not. For each secretary, he wrote out either the session number of his call or a 0 if this secretary wasn't talking via Spyke at that moment.

Help Polycarpus analyze these data and find out the number of pairs of secretaries that are talking. If Polycarpus has made a mistake in the data and the described situation could not have taken place, say so.

Note that the secretaries can correspond via Spyke not only with each other, but also with the people from other places. Also, Spyke conferences aren't permitted — that is, one call connects exactly two people.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^3) — the number of secretaries in Polycarpus's corporation. The next line contains n space-separated integers: id_1, id_2, ..., id_{n} (0 ≤ id_{i} ≤ 10^9). Number id_{i} equals the number of the call session of the i-th secretary, if the secretary is talking via Spyke, or zero otherwise.

Consider the secretaries indexed from 1 to n in some way.


-----Output-----

Print a single integer — the number of pairs of chatting secretaries, or -1 if Polycarpus's got a mistake in his records and the described situation could not have taken place.


-----Examples-----
Input
6
0 1 7 1 7 10

Output
2

Input
3
1 1 1

Output
-1

Input
1
0

Output
0



-----Note-----

In the first test sample there are two Spyke calls between secretaries: secretary 2 and secretary 4, secretary 3 and secretary 5.

In the second test sample the described situation is impossible as conferences aren't allowed.

Difficulty: interview

Starter code:

Solutions:
#scott http://codeforces.com/problemset/problem/291/A now? ok you start

n = int(input())
arr = list(map (int, input().split())) #scott

#for i in arr:
#    print (i)

cnt = 0 
clast, llast = -1, -1 #scott wait we need to sort

arr = sorted(arr)

bad = False #scott so now we just count # of pairs and make sure there's not 3 in a row right?ok
#so a neat thing you can do is just for x in arr
for i in arr:
    #print (i)
    if i > 0: #scott so last was the last one, llast was the second last one
        if i == clast :
            cnt += 1 #scott
            if clast == llast :
                bad = True #scott your turn
        llast = clast
        clast = i #scott
if bad == False:
    print (cnt) #scott
else:
    print(-1) #scott

#darn ii'm getting RTE test 1


n=int(input())
s=input().split()
for i in range(n):
    s[i]=int(s[i])
ans=0
done=False
for i in range(n):
    if(s[i]==0):
        continue
    n=s[i+1:].count(s[i])
    if(n==1):
        ans+=1
    elif(n>1):
        print(-1)
        done=True
        break

if(not done):
    print(ans)


import sys
my_file = sys.stdin
#my_file = open("input.txt", "r")
my_file.readline()
nums = [int(i) for i in my_file.readline().split(" ")]
speaking = 0
for i in nums:
    if i > 0:
        if nums.count(i) == 2:
            speaking += 1
        elif nums.count(i) > 2:
            speaking = -1
            break
if speaking > 0:
    print(int(speaking/2))
else:
    print(speaking)

n, s = int(input()), 0
t = list(map(int, input().split()))
p = set(t)
p.discard(0)
for i in p :
    k = t.count(i)
    if k == 2: s += 1
    elif k > 2:
        s = -1
        break
print(s)

def main(n, nums):
	data = {}
	Rn = range(n)
	answer = 0

	for i in Rn:
		item = str(nums[i])
		if item!='0':
			if item not in data:
				data[item]=0
			data[item]+=1

	for item in data.keys():
		val = data[item]
		if val==2:
			answer+=1
		elif val>2:
			return -1

	return answer

def init():
	n = int(input())
	nums = list(map(int, input().split()))

	print(main(n, nums))

init()

n=int(input())

C={}

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

for i in range(n):
    item=L[i]
    if(item in C):
        C[item].append(i)
    else:
        C[item]=[i]
valid=True
ans=0
for item in C:
    if(item==0):
        continue
    if(len(C[item])>2):
        valid=False
        ans=-1
        break
    if(len(C[item])==2):
       ans+=1

print(ans)


input()
d=input().split()
ans=0
for i in d:
    if(d.count(i)>2 and i!='0'):print(-1);break
    elif(d.count(i)==2 and i!='0'):ans+=1
else:print(ans//2)

n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n):
    if a[i] != 0:
        a = a[i:n]
        break

l = len(a)
c = [0]*l
c[0] = 1
for i in range(1, l):
    if a[i] != a[i-1]:
        c[i] = 1
    else:
        c[i] = c[i-1] + 1

if l == a.count(0):
    print(0)
elif c.count(1) + c.count(2) != l:
    print(-1)
else:
    print(c.count(2))



input()
a,i,c=input().split(),0,0
a.sort()
while i<len(a):
    j=a.count(a[i])
    if a[i]!='0':
        if j==2:
            c+=1
        elif j>2:
            c=-1
            break
    i+=j
print(c)


n=int(input())

y=input().split()
x=[int(f) for f in y]
z=x[:]
zeros=[]
while (z.count(0)>0):
    z.remove(0)
    zeros.append(0)
    

count=0
count1=0
q=list(set(z))
for i in range (0,len(q)):
    key=q[i]
    if (z.count(key)==2):
        count+=1
    if (z.count(key)==1):
        count=count
    if (z.count(key)>2):
        count1=count1-1
        break

if (count1==0):
    print (count)
else:
    print(-1)
    
    
        
    



    
    


    
    


t = int(input())
sec = list(map(int, input().split()))
total = 0
m = set(sec)
for i in m:
    if i == 0:
        continue
    if sec.count(i) > 2:
        print(-1)
        return
    if sec.count(i) == 2:
        total += 1
print(total)

__copyright__ = ''
__author__ = 'Son-Huy TRAN'
__email__ = "sonhuytran@gmail.com"
__doc__ = ''
__version__ = '1.0'


def count_sessions(sessions: list) -> int:
    session_dict = {}

    for session in sessions:
        if session == 0:
            continue

        session_count = session_dict.get(session, 0)

        if session_count >= 2:
            return -1

        session_dict[session] = session_count + 1

    count = 0

    for value in session_dict.values():
        if value >= 2:
            count += 1

    return count


def main() -> int:
    n_calls = int(input())
    sessions = [int(word) for word in input().split()]

    print(count_sessions(sessions))
    return 0


def __starting_point():
    exit(main())
__starting_point()

n = int(input())
s = list(map(int, input().split()))
x = set(s)

r = 0

for i in x:
    if i != 0:
        p = s.count(i)
        if p == 2:
            r += 1
        elif p > 2:
            print(-1)
            return

print(r)


n = int(input())
s = input().split()
d = {}
for i in s:
    d[i] = d.get(i, 0) + 1
ans = 0
for i in d:
    if i == '0':
        continue
    if d[i] == 2:
        ans += 1
    elif d[i] > 2:
        print('-1')
        break
else:
    print(ans)

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

res = 0
for x in set(calls):
    if calls.count(x) == 2 and x != 0:
        res += 1
    if calls.count(x) >= 3 and x != 0:
        res = -1
        break

print(res)

n = int(input())
d = list(map(int, input().split()))
calls = dict()
invalid = False
c = 0
for i in range(n):
    if d[i] > 0:
        if d[i] in calls.keys() : calls[d[i]] += 1
        else : calls[d[i]] = 1
        if calls[d[i]] == 2:
           c += 1
        elif calls[d[i]] == 3:
            invalid = True
            break
        
if invalid: print(-1)
else: print(c)

#July 4, 2014
secs=int(input())
calls=input().split(' ')
total=0
calls.sort()
false=0
for x in range(len(calls)-2):
    if calls[x]==calls[x+1] and calls[x]!='0':
        if calls[x+1]==calls[x+2] and calls[x+1]!='0':
            print(-1)
            false=1
            break
        else:
            total+=1
if false!=1:
    if len(calls)>=2:
        if calls[len(calls)-2]==calls[len(calls)-1] and calls[len(calls)-1]!='0':
            total+=1
    print(total)


import sys
import math

n = int(sys.stdin.readline())

id = [int(x) for x in (sys.stdin.readline()).split() if x != '0']

if(len(id) == 0):
    print(0)
    return

res = 0
id.sort()

v = id[0]
k = 1
for x in id[1:]:
    if(x == v):
        k += 1
    else:
        if(k == 2):
            res += 1
        elif(k > 2):
            print(-1)
            return
        v = x
        k = 1

if(k == 2):
    res += 1
elif(k > 2):
    print(-1)
    return  
    
print(res)      


from collections import Counter
n = int(input())
cnt = Counter(int(x) for x in input().split())
ans = 0
for (a, b) in list(cnt.items()):
	if a:
		if b == 2:
			ans += 1
		if b > 2:
			print(-1)
			return
print(ans)


from collections import Counter


def main():
    n = int(input())
    d = Counter(list(map(int, input().split())))
    d[0] = 0
    if max(d.values()) < 3:
        print(sum(_ == 2 for _ in list(d.values())))
        # print(Counter(d.values())[2])
    else:
        print(-1)


def __starting_point():
    main()

__starting_point()

from collections import Counter


def main():
    n = int(input())
    d = Counter(list(map(int, input().split())))
    d[0] = 0
    if max(d.values()) < 3:
        # print(sum(_ == 2 for _ in d.values()))
        print(Counter(list(d.values()))[2])
    else:
        print(-1)


def __starting_point():
    main()

__starting_point()

# coding: utf-8
n = int(input())
id = [int(i) for i in input().split() if i!='0']
id.sort()
ans = 0
while id:
    tmp = id.pop()
    if id and tmp == id[-1]:
        ans += 1
        id.pop()
    if id and tmp == id[-1]:
        ans = -1
        break
print(ans)


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

dct = {}
for i in lst:
    if i > 0:
        dct[i] = dct.get(i, 0) + 1

total = 0
for v in list(dct.values()):
    if v == 2:
        total += 1
    elif v > 2:
        total = -1
        break

print(total)


n = int(input())
s=0
l=input().split()

for i in range(n):
    l[i]=int(l[i])
r=0    
for i in range(n-1):
    r=0
    if(l[i]!=0):
        for j in range(i+1,n):
            if(l[i]==l[j]):
                r+=1
        if(r==1):
            s+=1
        elif(r>1):
            print(-1)
            break
if(r<=1):
    print(s)












n = int(input())
l = list(map(int,input().split()))
l.sort()
r = 0
bad = False
for i in range(n-1):
    if l[i] == 0 :
        continue
    if l[i] == l[i+1]:
        r += 1
    if i < n-2 and l[i+2] == l[i]:
        print(-1)
        bad = True
        break
if not bad :
    print(r)