Алексей, возможно, самый умный и при этом самый ленивый человек в мире. Сегодня он участвует в олимпиаде.
На олимпиаде участникам даны $$$n$$$ задач, за правильное решение $$$i$$$-й задачи, участник получит $$$a_i$$$ баллов, за неправильное решение баллов не дают. Дипломы призера дадут тем участникам, которые наберут хотя бы половину от суммарного числа баллов. Например, если на олимпиаде дано три задачи, стоимости которых в баллах равны $$$1$$$, $$$3$$$ и $$$4$$$, соответственно, для получения диплома призера достаточно набрать четыре балла.
Алексей пришел на олимпиаду с целью получить диплом призера. При этом Алексей очень умен и может правильно решить любую задачу на олимпиаде. Но в то же время Алексей очень ленив и хочет решить как можно меньше задач.
Алексей настолько ленив, что даже задачи, которые он будет решать, выбирает лениво. Он хочет выбрать некоторую задачу с номером $$$k$$$, а затем решать задачи с номерами $$$k, k+1, k+2 \ldots$$$ до тех пор, пока ему не будет хватать баллов на диплом призера. Максимум, на что готов Алексей, это пропустить одну задачу и не решать ее, чтобы решить в итоге еще меньше задач.
Зная стратегию Алексея и информацию о задачах олимпиады, определите минимальное количество задач, которые нужно решить Алексею, чтобы получить диплом призера.
В первой строке дано одно натуральное число $$$n$$$ — количество задач на олимпиаде ($$$1 \le n \le 10^5$$$).
Во второй строке заданы $$$n$$$ чисел $$$a_1, a_2, \dots a_n$$$ — стоимости каждой задачи в баллах ($$$1 \le a_i \le 10^9$$$).
Выведите одно число — минимальное количество задач, которые может решить Алексей, придерживаясь своей стратегии, чтобы получить диплом призера.
5 1 1 2 1 2
2
3 2 3 1
1
В первом тесте из примера для получения диплома призера необходимо набрать хотя бы четыре балла. Алексей может начать решать с третьей задачи, пропустить четвертую и набрать четыре балла, решив две задачи.
Во втором тесте достаточно решить только вторую задачу, набрав три балла.
