{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eImagine that you have a twin brother or sister. Having another person that looks exactly like you seems very unusual. It\u0027s hard to say if having something of an alter ego is good or bad. And if you do have a twin, then you very well know what it\u0027s like.\u003c/p\u003e\u003cp\u003eNow let\u0027s imagine a typical morning in your family. You haven\u0027t woken up yet, and Mom is already going to work. She has been so hasty that she has nearly forgotten to leave the two of her darling children some money to buy lunches in the school cafeteria. She fished in the purse and found some number of coins, or to be exact, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e coins of arbitrary values \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. But as Mom was running out of time, she didn\u0027t split the coins for you two. So she scribbled a note asking you to split the money equally.\u003c/p\u003e\u003cp\u003eAs you woke up, you found Mom\u0027s coins and read her note. \"But why split the money equally?\" — you thought. After all, your twin is sleeping and he won\u0027t know anything. So you decided to act like that: pick for yourself some subset of coins so that the sum of values of your coins is \u003cspan class\u003d\"tex-font-style-bf\"\u003estrictly larger\u003c/span\u003e than the sum of values of the remaining coins that your twin will have. However, you correctly thought that if you take too many coins, the twin will suspect the deception. So, you\u0027ve decided to stick to the following strategy to avoid suspicions: you take the \u003cspan class\u003d\"tex-font-style-bf\"\u003eminimum number of coins\u003c/span\u003e, whose sum of values is strictly more than the sum of values of the remaining coins. On this basis, determine what \u003cspan class\u003d\"tex-font-style-bf\"\u003eminimum\u003c/span\u003e number of coins you need to take to divide them in the described manner.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 100\u003c/span\u003e) — the number of coins. The second line contains a sequence of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e\u003c/span\u003e, ..., \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 100\u003c/span\u003e) — the coins\u0027 values. All numbers are separated with spaces.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eIn the single line print the single number — the minimum needed number of coins.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n3 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n2 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first sample you will have to take \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e coins (you and your twin have sums equal to \u003cspan class\u003d\"tex-span\"\u003e6, 0\u003c/span\u003e correspondingly). If you take \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e coin, you get sums \u003cspan class\u003d\"tex-span\"\u003e3, 3\u003c/span\u003e. If you take \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e coins, you get sums \u003cspan class\u003d\"tex-span\"\u003e0, 6\u003c/span\u003e. Those variants do not satisfy you as your sum should be strictly more that your twins\u0027 sum.\u003c/p\u003e\u003cp\u003eIn the second sample one coin isn\u0027t enough for us, too. You can pick coins with values \u003cspan class\u003d\"tex-span\"\u003e1, 2\u003c/span\u003e or \u003cspan class\u003d\"tex-span\"\u003e2, 2\u003c/span\u003e. In any case, the minimum number of coins equals \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e. \u003c/p\u003e"}}]}