Start: Jun, 27, 2019 08:30:00
2019年度暑期短学期第二天
End: Jun, 27, 2019 11:30:00
Time elapsed:
Time remaining:

曾小浪拿书 1828

Time Limit:  1 s      Memory Limit:   128 MB
Submission:108     AC:36     Score:0

Description

快要期末考试了。曾小浪共有n门课有考试,并为每门课分别准备了a1,a2,…,an本书。由于一天到晚在忙着复习,本来按课程顺序堆得整整齐齐的书都被她放得乱七八糟。
某天,她准备去恕园2-807把每门课的书都拿走2本。她拿书有三大怪癖:视力差,每次只有把书拿起才能获知其属于哪门课;力气小,每次只能拿1本书;很懒,拿起的书不会再放回。
小浪想知道,最坏情况下,需要拿多少次才能保证每门课的书都拿到2本。如果不可能完成,请输出-1。

Input

多组测试数据。
每组:
第一行输入n(1<=n<=100),以输入0为结束标志
第二行输入长度为n的整型数组a1,a2,…,an(0 <= ai <= 500)

Output

每组数据针对每组输入数据,输出一行包含一个整数表示需要拿多少次答案。

Samples

input
2 2 2 1 6 1 1 0
output
4 2 -1

Hint

第一组数据,他需要把所有书取出来
第二组数据,因为一共只有一门课,取出任意两本就好了。
第三组数据,因为永远不可能拿到2本