#CF451B. 数组排序
数组排序
CF451B Sort the Array
题目描述
作为一名程序员,你非常喜欢数组。在你生日时,你的朋友们送给你一个由 个互不相同的整数组成的数组 。
不幸的是,数组 的大小太小了,你想要一个更大的数组!你的朋友们同意,只要你能够正确回答下面这个问题,他们就会给你一个更大的数组:是否可以通过仅反转 的一个连续子段,就将数组 按升序排列?相关术语的定义见下方说明。
【名词解释】
子段:数组 的一个子段 是指 这一连续的元素序列;
反转:对于一个大小为 的数组 ,将其子段 反转后,得到的新数组如下:
$a_1, a_2, \dots, a_{l-2}, a_{l-1}, a_r, a_{r-1}, \dots, a_{l+1}, a_l, a_{r+1}, a_{r+2}, \dots, a_{n-1}, a_n$
输入格式
第一行输入一个整数 代表数组 的大小。
第二行输入 个互不相同的整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$,代表数组 中的元素。
输出格式
如果可以通过反转 的某一连续子段使数组按升序排列,先在第一行输出 ,再在第二行输出两个整数,代表需要反转的子段的起止下标(下标从 开始,且起始下标不能大于终止下标)。如果有多种选法,输出其中任意一种即可。
如果无法通过反转任意一段得到升序数组,则输出 。
测试样例
3
3 2 1
yes
1 3
样例 1 解释
你可以反转整个数组,得到 ,该数组已按升序排列。
4
2 1 3 4
yes
1 2
4
3 1 2 4
no
样例 3 解释
不存在可以反转使数组升序排列的子段。
2
1 2
yes
1 1