시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB131767259.504%

문제

As a huge fan of the popular collectible card game Numinous Wilds: the Elven Reign Chronicles (NWERC), you have a large collection of cards which you carefully organise by their rarity. One day you notice that someone has touched your collection, and that some of the cards are now out of order. The most natural suspect, of course, is your little brother Billy, who was absolutely 100% forbidden from playing with your cards. After a few minutes of interrogation Billy confesses that he indeed took a few consecutive cards from the middle of the stack, but he swears that he put them back in exactly the same order as they were. You suspect that Billy, being so young, may have simply mistakenly reversed the order of the cards that he took. Now you want to check your theory and decide if you can find the batch of cards that Billy took to play with.

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 ≤ n ≤ 106), the number of cards in your collection.
  • One line containing n integers v1, . . . , vn (1 ≤ vi ≤ 109 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.

예제 입력 1

7
10 13 19 19 15 14 20

예제 출력 1

3 6

예제 입력 2

6
9 1 8 2 7 3

예제 출력 2

impossible

예제 입력 3

3
1 2 3

예제 출력 3

2 2

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2019 I번

  • 문제를 만든 사람: Robin Lee