← 返回题目列表

Codeforces · 56/B

B. 被破坏的排列

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

Vasya 收集硬币:他从 1 到 n 每年恰好有一枚硬币。当然,瓦夏将他收藏的所有硬币按照发行的顺序保存起来。有一次,瓦夏的弟弟做出了改变——他把发行年份从l到r的所有硬币都拿走了,并按相反的顺序排列。也就是他把某个段[l,r]取反了。此时该线段的端点并不重合。例如,如果 n = 8,则最初 Vasya 的硬币保持顺序为 1 2 3 4 5 6 7 8。如果 Vasya 的弟弟选择了段 [2, 6],则反转后硬币顺序将变为 1 6 5 4 3 2 7 8。Vasya 怀疑其他人可能在他哥哥之后破坏了排列。帮助他找出答案。检查是否可以使用一个段反转从排列 1 2 ... n 获得给定的排列。如果可能的话,找到该段本身。

输入

第一行包含一个整数 n (1 ≤ n ≤ 1000),它是 Vasya 收藏的硬币数量。第二行包含空格分隔的 n 个整数,它们是损坏的硬币序列。保证给定的序列是一个排列,即它只包含从 1 到 n 的整数,并且每个数字恰好使用 1 次。

输出

如果不可能通过一次操作从原始排列获得给定的排列,则打印 0 0。否则,打印两个数字 l r (1 ≤ l < r ≤ n),它们是需要反转以从排列 1 2 ... n 获得给定排列的线段的端点。

示例

输入 #1

8
1 6 5 4 3 2 7 8

输出 #1

2 6

输入 #2

4
2 3 4 1

输出 #2

0 0

输入 #3

4
1 2 3 4

输出 #3

0 0