题目描述
空间站的舱室越来越多,有些太空舱在维护期间是不能进入的,常规的通讯手段也会因断电而无法使用。因此各舱之间有一台一次可以传输一个非负整数的机器。现在希望利用它传输 非空 的整数数列,为此定义一种通讯协议,用于各舱之间的应急通讯。
在传输前,双方事先约定一个整数作为保留字。传输时,连续三次出现保留字表示传输开始或结束,正文中每两个数字之间插入一个保留字。如数列 12345,约定保留字为 0,则一次完整的传输为 000102030405000。已知传输的正文不含保留字。
现在给出 n 个整数,它们是某台机器发送的数据的一段记录(可能不完整,只是其中片段,但一定连续且符合前述格式),试确定保留字或指出这段记录无法确定保留字。请注意,输入的记录段落中既 可能包含不止一次完整的传输,也可能是一次完整的传输中间的片段。
输入包含 T 组数据,各组数据之间是独立的。
输入格式
输入的第 1 行包含 1 个整数 T,表示数据组数。
接下来 2T 行,每 2 行描述一组数据。其中前一行是 1 个整数 n,表示下一行记录片段的长度;后一行是 n 个整数的值,表示发送的数据的一段记录。
输出格式
输出 T 行,每行 1 个整数,表示对应该组数据的保留字。如果根据所给的记录片段无法确定保留字,输出 −1。
输入输出样例
输入 #1
7 15 0 0 0 1 0 2 0 3 0 4 0 5 0 0 0 4 9 9 9 1 7 32 80 32 8 32 0 32 8 3 2 1 2 3 2 5 2 2 7 9 8 3 5 3 7 3 10 5 9 8 9 5 9 5 9 5 9 5
输出 #1
0 9 32 2 -1 -1 -1
说明/提示
数据范围
对于全部数据,有1 ≤ T ≤ 10,1 ≤ n ≤ 10000。输入数据中所有数均为不超过 10000 的非负整数。
测试点 1~2(共 20 分):保证记录段落中包含至少一次完整的传输。
测试点 3~6(共 40 分):保证所给的记录可以确定保留字。
测试点 7~10(共 40 分):无特殊限制。