题目描述

没头脑和不高兴正在玩一个纸牌游戏。

现在，不高兴手中拿着N张纸牌，编号 $1 \cdots N$ (排列顺序不一定是按照编号顺序排列)。$Domagoj$ 需要将一段连续的纸牌进行颠倒，旋转 $180°$ （将连续纸牌的第一张与最后一张交换位置，第二张与倒数第二张交换位置...以此类推）。

但是没头脑喜欢固定点，即纸牌的编号与位置相对应(编号为 $x$ 的纸牌刚好排在第 $x$ 个位置)，没头脑希望出现的固定点越多越好。

现在，请你帮助没头脑选择一段连续的纸牌进行颠倒，使得固定点的数目尽可能的多。

输入格式

第一行一个正整数 $N$ ，为 $Mate$ 手中的纸牌数。

第二行 $N$ 个数，为手中纸牌的编号。

输出格式

输出两个数正整数 $A,\ B$ ，表示将号码 $A$ 到号码 $B$ 之间的所有纸牌进行颠倒得到的固定点最多，如果有多种情况均满足条件，输出翻转纸牌最少的一种，如果翻转数目相同，输出 $A$ 最小的情况。

样例1输入

4
3 2 1 4 

样例1输出

3 1

样例2输入

2
1 2

样例2输出

1 1

样例1解释

将 $3\ 2\ 1$ 旋转后得到 $1\ 2\ 3$ ，此时固定的数目最多，有 $4$ 个。

数据范围

对于 $30$% 的数据，$1 \leq N \leq 500$ 。

对于 $60$% 的数据，$1 \leq N \leq 5000$ 。

对于 $100$% 的数据， $1 \leq N \leq 500000$ 。

大样例下载

百度网盘大样例下载 提取码: GFOI

阿里云盘大样例下载

夸克云盘大样例下载