뒤집힌 카드 더미
면접 대비시간 제한5초메모리 제한512 MB
주어진 수열에서 한 구간을 뒤집어 전체를 비내림차순으로 만들 수 있는지 판별하고, 가능하면 그 구간의 시작과 끝 위치를 출력한다.
문제
인기 있는 수집형 카드 게임 Numinous Wilds: the Elven Reign Chronicles (NWERC)의 열렬한 팬인 당신은 희귀도에 따라 카드를 꼼꼼히 정리한 큰 컬렉션을 가지고 있다. 어느 날 누군가 컬렉션을 건드려서 일부 카드의 순서가 뒤바뀐 것을 발견한다. 가장 유력한 용의자는 당연히 카드를 절대 만지지 못하게 했던 어린 동생 빌리다. 몇 분간 추궁하자 빌리는 더미 중간에서 연속된 카드 몇 장을 가져간 것은 인정하지만, 원래 순서 그대로 되돌려 놓았다고 주장한다. 당신은 어린 빌리가 가져간 카드의 순서를 실수로 뒤집었을 가능성이 있다고 본다. 이제 이 가설을 확인하고 빌리가 가지고 놀았던 카드 묶음을 찾아낼 수 있는지 판단하려 한다.
정확히 하나의 연속된 카드 묶음을 뒤집어서 카드를 희귀도 기준으로 비내림차순으로 정렬할 수 있는가?
입력
입력은 다음과 같다.
- 한 줄에 정수 n (1 ≤ n ≤ 106)이 주어진다. 이는 컬렉션에 있는 카드의 수다.
- 한 줄에 n개의 정수 v1, . . . , vn (모든 i에 대해 1 ≤ vi ≤ 109)이 주어진다. 이는 현재 카드 희귀도 값의 순서다.
출력
정확히 하나의 연속된 부분 수열을 뒤집어서 카드를 정렬할 수 있다면, 그 부분 수열의 1-based 시작 인덱스와 끝 인덱스를 출력한다. 그렇지 않으면 “impossible”을 출력한다. 가능한 답이 여러 개라면 그중 아무거나 출력해도 된다.