Задача Game2015. Два гравці грають у таку гру. Є набір з N чисел, які відомі учасникам. Перший повинен знайти найменше з них і збільшити його настільки, щоб воно стало рівним наступному за ним (за зростанням) числу. Другий гравець діє навпаки: знаходить найбільше число і зменшує його настільки, аби воно стало рівним наступному за спаданням числу. Гра триває, поки є хоча б 3 різних числа. Програє той гравець, який вже не може зробити черговий хід. Знаючи, що перший гравець завжди розпочинає гру, дізнайтеся, хто переможець в грі і значення найменшого та найбільшого числа, коли гру закінчено.
Технічні умови. Програма Game2015 читає з пристрою стандартного введення ціле число N (1<=N<=105) – кількість чисел, а далі через пропуски N цілих чисел, кожне з яких менше або дорівнює 105. Програма виводить на пристрій стандартного виведення 1, якщо перемагає перший гравець, 2 – якщо другий, а далі в тому ж рядку через пропуски 2 числа - найменше та найбільше число, коли гра завершиться.
Приклади
|
Введення |
Введення |
Введення |
|
3 3 3 3 |
4 3 1 2 1 |
7 2 1 3 3 5 4 1 |
|
Виведення |
Виведення |
Виведення |
|
2 3 3 |
2 1 2 |
2 2 3 |
Коментар. У першому прикладі 1-й гравець не може зробити початковий хід, отже другий є переможцем.