“那位女士说： ‘我已经骑了十五年马了，根本不可能把马蹄铁钉反！’ （……）”

“是的，那就是反的”——Domagoj 看着 Mate 的手牌低声说道。为了本题的目的，他们正在玩一个经过魔改的纸牌游戏《花火》（Hanabi）。简单起见，Mate 手里拿着 $N$ 张牌，牌上的数字按某种顺序为 $1, 2, \dots, N$。（每个 $1$ 到 $N$ 之间的数字恰好出现一次。）和玩真正的游戏时一样，他不能主动改变手牌的顺序。

为了让这个任务至少与故事有一点联系，Domagoj 会为 Mate 指出一个连续的子数组手牌。（他也可以只指向单张牌，但他至少会指向一张牌。）然后 Mate 会将该连续子数组“翻转”并放回原处。

（“翻转”可以理解为将给定子数组中的所有卡牌旋转 180 度。这意味着第一张牌和最后一张牌交换位置，第二张牌和倒数第二张牌交换位置，依此类推。）

和我们所有人一样，Domagoj 非常喜欢“不动点”（fixed points）。换句话说，就是卡牌上的数字与其在手牌中的位置相匹配（从 Domagoj 的左侧开始计数，即从 1 开始）。因此，他希望在翻转给定的子数组后，不动点的数量尽可能多。

请帮助 Domagoj 找出他需要指出哪一个连续子数组，使得 Mate 在翻转该子数组后，手牌中不动点的数量达到最大。

输入格式

输入的第一行包含一个正整数 $N$（$1 \le N \le 500\,000$），表示 Mate 手中卡牌的数量。

第二行包含 Mate 手中卡牌上的数字，顺序为 Domagoj 看到的顺序。

输出格式

输出单行，包含两个整数 $A$ 和 $B$，分别表示所需连续子数组开头和结尾的卡牌上的数字（按此顺序）。如果有多种选择，输出其中任意一种即可。

子任务

在占总分 30% 的测试数据中，满足 $N \le 500$。

在另外占总分 30% 的测试数据中，满足 $N \le 5000$。

样例

输入样例 1

4
3 2 1 4

输出样例 1

3 1

输入样例 2

2
1 2

输出样例 2

1 1

输入样例 3

7
3 6 5 7 4 1 2

输出样例 3

3 2

说明

在第一个样例中，翻转以 $3$ 开头、以 $1$ 结尾的连续子数组后，卡牌的顺序将变为 1 2 3 4，此时所有卡牌都是不动点。在这个样例中，给出的输出是唯一正确的输出。

在第二个样例中，翻转任何仅包含一张卡牌的子数组都会得到相同的卡牌顺序，这会产生最大数量的不动点。