몬스터 싸움
면접 대비시간 제한2초메모리 제한512 MB
두 몬스터가 죽을 때까지 싸워 살아남은 쪽의 전투력이 정확히 1이 되는 쌍을 찾아 선공 인덱스와 상대 인덱스를 출력하고, 없으면 impossible을 출력한다.
문제
Emma는 Gwint: A wizard's game이라는 새로운 카드 게임을 발견했다. 카드에는 몬스터 카드와 주문 카드 두 종류가 있다. 몬스터 카드는 점수를 얻는 데 쓰이고, 주문 카드는 대개 몬스터와 어떤 방식으로 상호작용한다.
각 몬스터 카드에는 정수 값이 적혀 있는데, 이것이 몬스터의 힘이다. 몬스터끼리 싸울 수 있으며, 싸울 때 힘은 몬스터의 공격력과 체력 역할을 모두 한다. 몬스터는 둘 중 하나가 죽을 때까지 번갈아 서로를 때린다. 몬스터 A가 몬스터 B를 때리면 B는 A의 힘만큼 힘을 잃는다. 반대로 B가 A를 때리면 A는 B의 힘만큼 힘을 잃는다(아래 예시 참고). 이 과정은 둘 중 하나의 힘이 0 이하가 될 때까지 계속되며, 그 순간 그 몬스터는 죽은 것으로 간주한다.
Images by OpenClipart-Vectors on Pixabay and from PhantomOpenEmoji.
Figure F.1: 몬스터 A와 B의 싸움. 처음 힘은 각각 4와 7이고 A가 먼저 때린다. B가 남은 힘 2로 이긴다.
Emma가 가장 아끼는 카드 중 하나는 Fight!라는 주문이다. 이 카드에는 다음과 같이 적혀 있다.
몬스터 두 마리를 고른다. 둘은 죽을 때까지 서로 싸운다. 살아남은 몬스터의 힘이 정확히 1이라면, 이 카드를 손으로 되돌린다.
Emma는 Fight!를 손으로 되돌려 받을 수 있도록 두 몬스터를 골라 최대한 효율적으로 플레이하고 싶다. 그런데 보드 위에 몬스터가 너무 많을 때가 많아서, 이것이 가능한지 알아내는 데 시간이 많이 걸린다. 카드를 되돌려 받을 수 있는 두 몬스터를 찾도록 도와줄 수 있는가?
입력
입력은 다음과 같다.
- 정수 n(2 ≤ n ≤ 105)이 있는 한 줄. n은 몬스터의 수이다.
- n개의 정수 m1, . . . , mn(1 ≤ mi ≤ 106)이 있는 한 줄. 각 몬스터의 힘을 나타낸다.
출력
Emma가 고를 수 있는 몬스터 쌍이 없으면 impossible을 출력한다. 그렇지 않으면 서로 다른 두 정수 i, j(1 ≤ i, j ≤ n)를 출력한다. i는 싸움을 시작하는 몬스터의 번호이고 j는 다른 몬스터의 번호이다. 답이 여러 개면 그중 아무거나 출력해도 된다.