Стоило всем в лагере уснуть, как Кирилл выбрался из палатки и отправился к Мудрому Дубу собирать грибы.
Известно, что под Дубом растет \(n\) грибов, каждый из которых обладает характеристикой \(v_i\) — волшебностью. Кирилл очень хочет приготовить из грибов магический эликсир максимальной силы.
Сила эликсира равна произведению количества входящих в него грибов на минимальную из волшебностей этих грибов. Для приготовления эликсира Кирилл будет последовательно срывать по одному грибу, растущему под Дубом. Кирилл может собирать грибы в любом порядке.
Однако не все так просто. Мудрый Дуб сообщил Кириллу перестановку чисел \(p\) от \(1\) до \(n\). Если Кирилл соберёт всего \(k\) грибов, то волшебность всех грибов с индексами \(p_1, p_2, \dots, p_{k - 1}\) станет равна \(0\). Грибы с нулевой волшебностью Кирилл не будет использовать для приготовления эликсира.
Ваша задача состоит в том, чтобы помочь Кириллу набрать грибы так, чтобы сварить эликсир максимальной возможной силы. Однако, Кириллу немного страшно надолго оставаться у дуба, поэтому из всех подходящих вариантов собрать грибы он просит вас найти тот, количество грибов в котором минимально.
Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Выходные данные
Для каждого набора входных данных выведите через пробел два целых числа — максимальную силу эликсира, который можно сварить, и минимальное число грибов, которые Кириллу нужно для этого использовать.
Примечание
В первом примере нужно взять грибы под индексами \(1\) и \(2\), таким образом сила эликсира равна \(2 \cdot \min(a_1, a_2) = 2 \cdot \min(9, 8) = 2 \cdot 8 = 16\). Обратите внимание, что волшебность гриба с индексом \(3\) после срывания двух грибов станет равна \(0\).