У Мислава был массив \(a_1\), \(a_2\), \(\cdots\), \(a_n\) из \(n\) целых положительных чисел, но он его потерял. Он помнит следующие сведения о массиве:
- Количество различных чисел в массиве не меньше \(l\) и не больше \(r\);
- Для любого элемента массива \(a_i\) верно одно из двух: либо \(a_i = 1\), либо \(a_i\) чётно, и в массиве есть число \(\dfrac{a_i}{2}\).
Например, при \(n=5\), \(l=2\), \(r=3\) массив мог быть таким: \([1,2,2,4,4]\) или таким: \([1,1,1,1,2]\), но не мог быть таким: \([1,2,2,4,8]\), потому что такой массив содержит \(4\) различных числа, не мог быть таким: \([1,2,2,3,3]\), потому что число \(3\) — нечётное и не равно \(1\), и не мог быть таким: \([1,1,2,2,16]\), потому что в массиве есть число \(16\), и нет числа \(\frac{16}{2} = 8\).
На основании этих данных он просит вас посчитать минимальную возможную сумму чисел в массиве и максимальную возможную сумму чисел в массиве.
Примечание
В первом примере массив может выглядеть так: \([1,1,1,2]\), \([1,1,2,2]\) или \([1,2,2,2]\). В первом случае достигается минимальная сумма, в последнем — максимальная.
Во втором примере минимальная сумма достигается при массиве \([1,1,1,1,1]\), максимальная — при \([1,2,4,8,16]\).