451B.md (2037B)
1 Source: https://codeforces.com/problemset/problem/451/B 2 3 B. Sort the Array 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Being a programmer, you like arrays a lot. For your birthday, your friends have given you an array *a* consisting of *n* distinct integers. 22 23 Unfortunately, the size of *a* is too small. You want a bigger array! Your friends agree to give you a bigger array, but only if you are able to answer the following question correctly: is it possible to sort the array *a* (in increasing order) by reversing exactly one segment of *a*? See definitions of segment and reversing in the notes. 24 25 Input 26 27 The first line of the input contains an integer *n* (1 ≤ *n* ≤ 105) — the size of array *a*. 28 29 The second line contains *n* distinct space-separated integers: *a*[1], *a*[2], ..., *a*[*n*] (1 ≤ *a*[*i*] ≤ 109). 30 31 Output 32 33 Print "yes" or "no" (without quotes), depending on the answer. 34 35 If your answer is "yes", then also print two space-separated integers denoting start and end (start must not be greater than end) indices of the segment to be reversed. If there are multiple ways of selecting these indices, print any of them. 36 37 Examples 38 39 Input 40 41 ``` 42 3 43 3 2 1 44 ``` 45 46 Output 47 48 ``` 49 yes 50 1 3 51 ``` 52 53 Input 54 55 ``` 56 4 57 2 1 3 4 58 ``` 59 60 Output 61 62 ``` 63 yes 64 1 2 65 ``` 66 67 Input 68 69 ``` 70 4 71 3 1 2 4 72 ``` 73 74 Output 75 76 ``` 77 no 78 ``` 79 80 Input 81 82 ``` 83 2 84 1 2 85 ``` 86 87 Output 88 89 ``` 90 yes 91 1 1 92 ``` 93 94 Note 95 96 Sample 1. You can reverse the entire array to get [1, 2, 3], which is sorted. 97 98 Sample 3. No segment can be reversed such that the array will be sorted. 99 100 Definitions 101 102 A segment [*l*, *r*] of array *a* is the sequence *a*[*l*], *a*[*l* + 1], ..., *a*[*r*]. 103 104 If you have an array *a* of size *n* and you reverse its segment [*l*, *r*], the array will become: 105 106 *a*[1], *a*[2], ..., *a*[*l* - 2], *a*[*l* - 1], *a*[*r*], *a*[*r* - 1], ..., *a*[*l* + 1], *a*[*l*], *a*[*r* + 1], *a*[*r* + 2], ..., *a*[*n* - 1], *a*[*n*].