eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Боевые монстры

Боевые монстры

Эмма только что открыла для себя новую карточную игру под названием "Гвинт: игра волшебника". Есть два типа карт: карты монстров и карты заклинаний. Карты монстров используются для набора очков, а карты заклинаний обычно каким-то образом взаимодействуют с монстрами. На каждой карте монстра указано целое значение --- сила монстра. Монстры могут сражаться друг с другом, и во время этих боев сила действует как здоровье монстра. Монстры по очереди бьют друг друга, пока один из них не умрет. Всякий раз, когда монстр $A$ сталкивается с монстром $B$, это приводит к тому, что $B$ теряет количество силы, равное силе $A$. И наоборот, если $B$ попадает в $A$, $A$ теряет силу, равную силе $B$ (см. пример ниже). Это продолжается до тех пор, пока сила одного из двух монстров не станет равна нулю или меньше, после чего этот монстр считается мертвым. \includegraphics{https://eolympusercontent.com/images/7oa62mrmp5687498ccvumcss2g.gif} Бой между монстрами $A$ и $B$ начинается с сил $4$ и $7$ соответственно. $A$ бьет первым. $B$ побеждает с оставшейся силой $2$. Одна из самых любимых карт Эммы в игре --- заклинание под названием "Fight!" в котором говорится: \begin{itemize} \item Выберите двух монстров. Они сражаются друг с другом насмерть. Если у выжившего монстра осталась сила ровно $1$, то верните эту карту участнику. \end{itemize} Конечно, Эмме хотелось бы сыграть максимально эффективно, подобрав таких двух монстров, чтобы заклинание "Fight!" возвращало ей карту. Однако на доске часто бывает много монстров, из-за чего выяснение того, можно ли это сделать или нет, занимает очень много времени. Сможешь ли ты помочь ей найти двух монстров, которых она сможет выбрать, чтобы вернуть карту? \InputFile Первая строка содержит количество монстров $n~(2 \le n \le 10^5)$. Следующая строка содержит $n$ целых чисел $m_1, ..., m_n~(1 \le m_i \le 10^6)$, описывающих силу каждого монстра. \OutputFile Если нет пары монстров, которых Эмма могла бы выбрать, выведите \textbf{impossible}. В противном случае выведите два различных целых числа $i, j~(1 \le i, j \le n)$, где $i$ --- номер монстра, начавшего бой, а $j$ --- номер другого монстра. Если существует несколько решений, выведите любое из них.
Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4
1 12 67 8
Вихідні дані #1
impossible
Вхідні дані #2
5
1 1 12 67 8
Вихідні дані #2
2 1
Вхідні дані #3
6
1 5 6 7 90 8
Вихідні дані #3
2 6
Джерело 2018 ICPC German Collegiate Programming Contest (GCPC), Задача F