P10883 [COCI 2017/2018 #2] Doktor

搬运自 [COCI 2017/2018 Contest #2](https://hsin.hr/coci/archive/2017_2018/) T3「Doktor」，[原题题面](https://hsin.hr/coci/archive/2017_2018/contest2_tasks.pdf)。 Special Judge 由搬题人提供，如果有锅请私信，谢谢。

> 夫人说： > >「我已经骑马十五年了，不可能把马倒着钉蹄铁！」 > > （……） 「是的，那是倒着的。」——多马戈伊低声说道，看着马特的手，正在玩一个经过大幅修改的纸牌游戏 Hanabi。为了简单起见，马特手中有 $N$ 张牌，按顺序编号为 $1, 2, \dots, N$。 每个数字从 $1$ 到 $N$ 恰好出现一次。就像玩真正的游戏一样，他不能主动改变牌的顺序。 为了让任务至少与故事有些关联，多马戈伊会指向马特手中一段连续的牌子序列。（他也可以指向单张牌，但至少会指向一张牌。）然后马特将「旋转」该连续子数组并放回去。 （旋转可以被认为是将给定子数组中的所有牌旋转 180 度。这意味着第一张和最后一张牌交换位置，第二张和倒数第二张牌交换位置，依此类推。） 和我们所有人一样，多马戈伊非常喜欢不动点。换句话说，就是牌的数字与它们在手中的位置相匹配的牌，从多马戈伊的左侧开始计数。因此，他希望在旋转给定子数组后，不动点的数量尽可能多。 帮助多马戈伊找出他需要指出哪一段连续子数组，以便在旋转该子数组后，马特手中的不动点数量达到最大。

输入的第一行包含正整数 $N (1 \leq N \leq 500000)$，表示马特手中的牌数。 接下来的行包含多马戈伊看到的马特手中牌的顺序。

你必须输出一行，包含 $A$ 和 $B$，即所需连续子数组的起始和结束牌上的数字，按此顺序。如果有多个选项，输出其中任意一个。

在第一个测试用例中，旋转从 3 开始到 1 结束的连续子数组后，牌的顺序将变为 1 2 3 4，现在所有的牌都是不动点。在这个例子中，给定的输出是唯一正确的输出。 在第二个测试用例中，旋转任何仅包含一张牌的子数组会导致相同的牌顺序，这种顺序产生最大数量的不动点。（由 ChatGPT 4o 翻译）