Simulation - Concursul Național de Informatică 2024 | ra

Se dă $n$ și un șir $a_1, a_2, \dots a_n$ de numere naturale. Inițial, toate numerele sunt colorate în $\textcolor{red}{roșu}$. Într-o operație, poți să alegi un număr $\textcolor{red}{roșu}$ și să îl faci $\textcolor{blue}{albastru}$.

Cerință

Află numărul minim de operații pe care trebuie să le faci astfel încât suma numerelor $\textcolor{blue}{albastre}$ să fie strict mai mare decât suma numerelor $\textcolor{red}{roșii}$.

Date de intrare

Pe prima linie a fișierului de intrare ra.in se află numărul $n$. Pe a doua linie se află șirul $a_1, a_2, \dots, a_n$.

Date de ieșire

Să se afișeze în fișierul ra.out numărul minim de operații astfel încât suma numerelor albastre să fie strict mai mare decât suma celor roșii.

Restricții și precizări

• $2 \leq n \leq 10 \ 000$
• $1 \leq a_i \leq 10^9$

Exemplul 1

ra.in

5
2 4 2 6 7

ra.out

2

Explicație

La primul exemplu, inițial șirul arată astfel: $\textcolor{red}{2 \ 4 \ 2 \ 6 \ 7}$.

Suma valorilor roșii este $2 + 4 + 2 + 6 + 7 = 21$.

Suma valorilor albastre este $0$ (deoarece nu am colorat niciun element în albastru).

În prima operație, vom alege elementul de pe a doua poziție să îl colorăm în albastru.

Acum șirul nostru arată astfel: $\textcolor{red}{2} \ \textcolor{blue}{4} \ \textcolor{red}{2 \ 6 \ 7}$. Suma valorilor roșii este $2 + 2 + 6 + 7 = 17$, iar suma valorilor albastre este $4$.

În a doua operație, vom alege elementul de pe ultima poziție și îl vom colora în albastru.

Șirul devine: $\textcolor{red}{2} \ \textcolor{blue}{4} \ \textcolor{red}{2 \ 6} \ \textcolor{blue}{7}$. Are suma valorilor roșii $2 + 2 + 6 = 10$ și suma valorilor albastre $4 + 7 = 11$. Deci, suma valorilor $\textcolor{blue}{albastre}$ este strict mai mare decât a celor $\textcolor{red}{roșii}$.

Observăm că dacă am fi colorat numerele $6$ și $7$ în albastru, am obține o altă soluție cu $2$ operații.

Exemplul 2

ra.in

10
6 3 8 4 5 6 5 5 7 5

ra.out

5

Explicație

Pentru al doilea exemplu, obținem o soluție cu $5$ operații dacă colorăm valorile $8$, $7$, $6$, $6$, $5$ (observăm că doar unul dintre valorile de $5$ va fi colorat în albastru).