如果一个下标从 0 开始、长度为 $n$ 的数组 $a$ 满足对于任意下标 $i$ ($0 \le i < n$) 都有 $a[i] = a[n - 1 - i]$，则称其为回文数组。

给定一个数组，你的任务是向其中恰好插入一个元素使其成为回文数组，或者判断这是不可能的。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示数组的长度。

第二行包含 $n$ 个整数 $a_0, a_1, \dots, a_{n-1}$ ($-10^9 \le a_i \le 10^9$)。

输出格式

如果无法通过恰好插入一个整数使数组成为回文数组，输出 -1。

否则，输出两个整数：插入元素在新数组中的下标 $k$ ($0 \le k \le n$) 以及该元素的值 $v$ ($-10^9 \le v \le 10^9$)。

例如，如果你在开头插入一个元素，则 $k = 0$；如果你在 $a[i - 1]$ 和 $a[i]$ 之间插入一个元素，则 $k = i$；如果你在末尾插入一个元素，则 $k = n$。

如果有多种方法可以通过插入一个元素使原数组成为回文数组，你可以选择其中任意一种。

样例

输入样例 1

2
20 18

输出样例 1

2 20

输入样例 2

1
-2018

输出样例 2

0 -2018

输入样例 3

4
2 0 1 8

输出样例 3

-1

输入样例 4

2
8 8

输出样例 4

1 2018

说明

• 在第一个样例中，你在数组末尾添加 20，得到回文数组 20 18 20。
• 在第二个样例中，你在数组开头添加 -2018，得到回文数组 -2018 -2018。
• 在第三个样例中，你无法通过插入一个元素使数组成为回文数组，因此答案为 -1。
• 在第四个样例中，你可以在两个 8 之间插入任意整数，因为对于任意 $x$，8 x 8 都是回文的。因此这里选择插入 2018。