#CF451B. 数组排序

数组排序

CF451B Sort the Array

题目描述

\hspace{15pt}作为一名程序员,你非常喜欢数组。在你生日时,你的朋友们送给你一个由 nn 个互不相同的整数组成的数组 aa。

\hspace{15pt}不幸的是,数组 aa 的大小太小了,你想要一个更大的数组!你的朋友们同意,只要你能够正确回答下面这个问题,他们就会给你一个更大的数组:是否可以通过仅反转 aa 的一个连续子段,就将数组 aa 按升序排列?相关术语的定义见下方说明。

\hspace{15pt}【名词解释】

∙ \hspace{23pt}\bullet\,子段:数组 aa 的一个子段 [l,r][l, r] 是指 al,al+1,…,ara_l, a_{l+1}, \dots, a_r 这一连续的元素序列;

∙ \hspace{23pt}\bullet\,反转:对于一个大小为 nn 的数组 aa,将其子段 [l,r][l, r] 反转后,得到的新数组如下:

$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$

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦105)n \left(1 \leqq n \leqq 10^5\right) 代表数组 aa 的大小。

\hspace{15pt}第二行输入 nn 个互不相同的整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$,代表数组 aa 中的元素。

输出格式

\hspace{15pt}如果可以通过反转 aa 的某一连续子段使数组按升序排列,先在第一行输出 "yes"\texttt{"yes"},再在第二行输出两个整数,代表需要反转的子段的起止下标(下标从 11 开始,且起始下标不能大于终止下标)。如果有多种选法,输出其中任意一种即可。

\hspace{15pt}如果无法通过反转任意一段得到升序数组,则输出 "no"\texttt{"no"}。

测试样例

3
3 2 1
yes
1 3

样例 1 解释

\hspace{15pt}你可以反转整个数组,得到 [1,2,3][1, 2, 3],该数组已按升序排列。

4
2 1 3 4
yes
1 2
4
3 1 2 4
no

样例 3 解释

\hspace{15pt}不存在可以反转使数组升序排列的子段。

2
1 2
yes
1 1