欧几里得序列与两个数

题目描述

对于两个正整数 $x \geq y$，定义其长度为 $k$（$k \geq 2$）的欧几里得算法序列为如下正整数序列：

其中 $a_1 = x$，$a_2 = y$，且对任意 $1 \leq i \leq k - 2$，满足

这里 $u \bmod v$ 表示 $u$ 除以 $v$ 的非负余数。注意序列中每一项都必须是正整数。

例如，$x = 13, y = 8, k = 4$ 时，对应的欧几里得算法序列为 $a = [13, 8, 5, 3]$（$a_3 = 13 \bmod 8 = 5$，$a_4 = 8 \bmod 5 = 3$）。

现在给定一个序列 $b_1, b_2, \ldots, b_n$。请你判断：是否能将 $b$ 的元素重新排列，使得它成为某一组正整数 $x \geq y$ 的欧几里得算法序列？若能，输出对应的 $x, y$（$x \geq y$）；若不能，输出 $-1$。若有多个合法的 $x, y$，输出任意一组即可。

输入格式

每个测试点包含多组测试数据。第一行一个正整数 $t$（$1 \leq t \leq 500$），表示测试数据组数。

每组数据两行：

• 第一行一个正整数 $n$（$2 \leq n \leq 100$），表示序列长度。
• 第二行 $n$ 个正整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 10^9$），表示序列 $b$。

输出格式

对于每组数据，若存在合法的 $x, y$，输出一行两个正整数 $x, y$（$x \geq y$），用一个空格分隔；否则输出一行一个整数 $-1$。

样例输入 #1

6
2
1 1
2
1 2
4
1 2 3 4
3
6 4 2
4
3 8 13 5
3
1 1 1

样例输出 #1

1 1
2 1
-1
6 4
13 8
-1

样例解释

• 第 1 组数据：取 $x = 1, y = 1$，长度 $k = 2$ 的序列为 $[1, 1]$，与 $b$ 相等，合法。
• 第 3 组数据：可以证明不存在任何合法的 $x, y$，输出 $-1$。
• 第 4 组数据：取 $x = 6, y = 4, k = 3$，序列为 $[6, 4, 2]$（$a_3 = 6 \bmod 4 = 2$），与 $b$ 相等，合法。
• 第 6 组数据：$b = [1, 1, 1]$。若 $k \geq 3$，则需要 $a_1 > a_2$ 才能保证 $a_3 = a_1 \bmod a_2 \geq 1$，但 $b$ 中最大的两个数相等，无法满足，输出 $-1$。

数据范围

保证每组数据中 $\sum n$ 不会过大。

知识点与难度

本题涉及的知识点从属于 GESP 五级（数论：模运算 / 欧几里得算法 / 序列性质分析、排序），难度等级：普及/提高-。核心难点在于观察到序列的前两项必然是整个序列中最大的两个数，且后续各项由取模递推唯一确定、严格递减、可在模为 $0$ 之前任意截断。