Когда Зельду бросили в тюрьму самозванцы, притворяющиеся королем и министром Хайрула, ей было долгое время нечем заняться. Поэтому она выписала последовательность из n натуральных чисел, после чего стала выполнять с ней следующие действия:
Как только в последовательности останется не более двух различных чисел, Зельде надоест развлекаться с ней, и она наконец-то начнет предпринимать попытки сбежать из тюрьмы.
Чтобы ускорить этот процесс, определите, на каком ходу последовательность перестанет быть интересна Зельде, и какие значения в ней после этого останутся.
В первой строке ввода дано целое число n — количество чисел в последовательности (1 ≤ n ≤ 105).
Во второй строке перечислены n целых чисел ai — сами элементы последовательности (1 ≤ ai ≤ 105).
В первой строке выведите номер хода, после которого Зельде перестанет быть интересна последовательность. Если последовательность с самого начала не является интересной, выведите 0.
Во второй строке выведите через пробел минимальное и максимальное числа в получившейся последовательности.
3
4 5 6
1
5 6
4
1 2 1 3
2
1 2
6
4 2 2 5 1 3
6
2 3