Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно вычислить минимальную длину массива. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Ирис хранит целочисленный массив $$$a_1, a_2, \ldots, a_n$$$. Она знает, что этот массив обладает интересным свойством: максимальное абсолютное значение всех элементов меньше или равно сумме всех элементов, то есть $$$\max(\lvert a_i\rvert) \leq \sum a_i$$$.

Ирис определяет скучность массива как максимальную сумму его подмассива$$$^{\text{∗}}$$$.

Приближается день рождения Ирис, и Виктор собирается прислать ей ещё один массив $$$b_1, b_2, \ldots, b_m$$$. По некоторым, казалось бы, очевидным причинам он решает, что массив $$$b_1, b_2, \ldots, b_m$$$ должен обладать следующими свойствами.

• $$$a_1, a_2, \ldots, a_n$$$ должен быть подпоследовательностью$$$^{\text{†}}$$$ из $$$b_1, b_2, \ldots, b_m$$$.
• Эти два массива имеют одинаковую сумму. То есть, $$$\sum\limits_{i=1}^n a_i = \sum\limits_{i=1}^m b_i$$$.
• Значение скучности массива $$$b_1, b_2, \ldots, b_m$$$ является наименьшим из возможных.
• Среди массивов с наименьшей скучностью длина массива $$$b$$$ (т.е. $$$m$$$) является наименьшей из возможных. В этом случае Ирис поймёт его уважение как можно скорее!

Даже при таких ограничениях, как указано выше, всё равно существует слишком много возможных подарков. Поэтому Виктор просит вас вычислить значение $$$\boldsymbol{m}$$$ любого массива $$$b_1, b_2, \ldots, b_m$$$, удовлетворяющего всем вышеприведенным условиям. Он обещает вам: если вы успешно поможете ему, он поделится с вами кусочком праздничного торта Ирис.

Обратите внимание: поскольку входные данные большие, вам, возможно, потребуется оптимизировать их для решения этой задачи.

Например, в C++ достаточно использовать следующие строки в начале функции main():

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
}