← 返回题目列表

Codeforces · 252/B

B. 取消数组排序

中文机器翻译题面 查看原题

小 Petya 非常喜欢整数数组。最近,他的母亲给了他一个这样的由 n 个元素组成的数组。 Petya 现在想知道他是否可以交换数组中任意两个不同的整数,以便数组不排序。请注意,Petya 无法交换相等的整数,即使它们位于数组中的不同位置。另请注意,即使原始数组满足所有要求,Petya 也必须交换两个整数。

由n个元素组成的数组a(数组元素从1开始索引)如果至少满足以下两个条件之一,则称为排序:

1. a1 ≤ a2 ≤ ... ≤ an;
2. a1 ≥ a2 ≥ ... ≥ an。

帮助 Petya 找到需要交换的两个位置,否则说明它们不存在。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105)。第二行包含 n 个非负空格分隔整数 a1, a2, ..., an — Petya 的母亲向他提供的数组的元素。输入中的所有整数不超过 109。

输出

如果存在一对位置使得数组在交换时未排序,则打印这些位置的数字,并用空格分隔。如果有多对位置,则打印其中任意对。如果这样的对不存在,则打印-1。数组中的位置用 1 到 n 的整数进行编号。

示例

输入 #1

1
1

输出 #1

-1

输入 #2

2
1 2

输出 #2

-1

输入 #3

4
1 2 3 4

输出 #3

1 2

输入#4

3
1 1 1

输出#4

-1

注意

在前两个示例中,所需的对显然不存在。

在第三个示例中,您可以交换前两个元素。之后,数组将如下所示:2 1 3 4。该数组未排序。