Is it possible to restore the order of the cards into non-decreasing order of their rarity by reversing just one contiguous batch of cards?
The input consists of:
One line containing an integer $n$ ($1 \le n \le 10^6$), the number of cards in your collection.
One line containing $n$ integers $v_1, \ldots , v_ n$ ($1 \le v_{i} \le 10^9$ for all $i$), the current order of the cards’ rarity values.
If the cards can be sorted by reversing exactly one contiguous subsequence of the list, then output the $1$-based start and end indices of such a subsequence. Otherwise, output “impossible”. If there are multiple valid solutions you may output any one of them.
Sample Input 1 | Sample Output 1 |
---|---|
7 10 13 19 19 15 14 20 |
3 6 |
Sample Input 2 | Sample Output 2 |
---|---|
6 9 1 8 2 7 3 |
impossible |
Sample Input 3 | Sample Output 3 |
---|---|
3 1 2 3 |
2 2 |