Два скучающих солдата играют в карточную войну (эквивалент карточной игры «пьяница» в англоязычных странах). Их колода состоит ровно из n карт, пронумерованных различными числами от 1 до n. Исходно они делят между собой картны некоторым образом, возможно, не равным образом.
Правила игры следующие. На каждом ходу происходит сражение. Каждый игрок берет карту с вершины своей стопки и кладет на стол. Тот, у кого значение карты больше, выигрывает в этом сражении, берет обе карты со стола и кладет в низ своей стопки. Точнее говоря, сперва он берет карту противника и кладет в низ своей стопки, затем кладет свою карту в низ своей стопки. Если после какого-то хода стопка одного игрока становится пустой, то он проигрывает, а другой игрок побеждает.
Вам надо подсчитать, после сколько будет сражений и кто победит, в противном случае надо сказать, что игра не прекратится.
Выходные данные
Если кто-то победит в этой игре, выведите 2 целых чисел, где первое число обозначает количество сражений в игре, а второе — 1 или 2, обозначающее, какой игрок победил.
Если игра не закончится, а будет продолжаться вечно, выведите - 1.
Примечание
Первый пример:
Второй пример:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 1 3
2 4 2
|
6 2
|
|
2
|
3
1 2
2 1 3
|
-1
|