Дан массив \(a\) длины \(n\) и число \(x\). Вы можете проделать следующую операцию произвольное (возможно нулевое) число раз: выбрать любые два соседних элемента и заменить их на их сумму. При этом длина массива уменьшается на один. Например, если исходный массив был равен \([3, 6, 9]\), то за одну операцию его можно превратить в массив \([9, 9]\) или в массив \([3, 15]\).
Красотой массива \(b=[b_1, \ldots, b_k]\) назовём \(\sum_{i=1}^k \left\lceil \frac{b_i}{x} \right\rceil\). Иначе говоря, каждый элемент массива делят на \(x\), округляя результат вверх, и полученные числа суммируются. Например, для \(x = 3\) красота массива \([4, 11, 6]\) равна \(\left\lceil \frac{4}{3} \right\rceil + \left\lceil \frac{11}{3} \right\rceil + \left\lceil \frac{6}{3} \right\rceil = 2 + 4 + 2 = 8\). Определите, какое наименьшее и наибольшее значение красоты можно получить, преобразовав данный массив с помощью операций выше.
Выходные данные
Для каждого из наборов входных данных выведите два числа — минимальное и максимальное значение красоты, которые можно получить.
Примечание
В первом наборе входных данных красота массива не меняется при выполнении операций замены.
Во втором наборе входных данных для достижения максимальной красоты можно оставить массив без изменений, а для достижения минимальной — объединить элементы \(4\) и \(11\), получив массив \([6, 15]\), красота которого равна \(7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3 3
3 6 9
3 3
6 4 11
|
6 6
7 8
|