{"trustable":false,"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":"Дан массив целых чисел. Вася может переставлять его числа местами. При этом он хочет, чтобы как можно больше чисел стояли там, где раньше стояли меньшие числа. Помогите ему найти максимальное количество таких чисел.\n\nНапример, если нам дан массив [10,20,30,40], мы можем переставить числа так, что массив станет [20,40,10,30]. При этом на первой и второй позициях числа стали больше (20\u003e10, 40\u003e20), а на третьей и четвёртой — нет, значит для такой перестановки число, которое хочет максимизировать Вася, равно 2. Ознакомьтесь с примечанием к первому тестовому примеру, там разобран ещё один показательный тест.\n\nПомогите Васе так переставить числа, чтобы количество позиций, в которых в новом массиве числа больше, чем в изначальном, было максимальным."}},{"title":"Input","value":{"format":"HTML","content":"Первая строка содержит одно целое число n (1≤n≤10^5) — размер массива.\n\nВторая строка содержит n целых чисел a1,a2,…,an (1≤ai≤10^9) — элементы массива."}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"output-specification\"\u003e\u003cdiv class\u003d\"section-title\"\u003eВыходные данные\u003c/div\u003e\u003cp\u003eВыведите одно целое число\u0026nbsp;— максимальное число элементов массива, которые после перестановки будут стоять на позициях, где изначально стоял меньший элемент.\u003c/p\u003e\u003c/div\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e7\u003cbr\u003e10 1 1 1 5 5 3\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e4\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e5\u003cbr\u003e1 1 1 1 1\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e0\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cdiv class\u003d\"note\"\u003e\u003cdiv class\u003d\"section-title\"\u003eПримечание\u003c/div\u003e\u003cp\u003eВ первом тесте одна из оптимальных перестановок\u0026nbsp;— \u003cspan class\u003d\"MathJax_Preview\" style\u003d\"color: inherit;\"\u003e\u003c/span\u003e\u003cspan class\u003d\"MathJax\" id\u003d\"MathJax-Element-11-Frame\" tabindex\u003d\"0\" data-mathml\u003d\"\u003cmath xmlns\u003d\u0026quot;http://www.w3.org/1998/Math/MathML\u0026quot;\u003e\u003cmo stretchy\u003d\u0026quot;false\u0026quot;\u003e[\u003c/mo\u003e\u003cmn\u003e1\u003c/mn\u003e\u003cmo\u003e,\u003c/mo\u003e\u003cmn\u003e5\u003c/mn\u003e\u003cmo\u003e,\u003c/mo\u003e\u003cmn\u003e5\u003c/mn\u003e\u003cmo\u003e,\u003c/mo\u003e\u003cmn\u003e3\u003c/mn\u003e\u003cmo\u003e,\u003c/mo\u003e\u003cmn\u003e10\u003c/mn\u003e\u003cmo\u003e,\u003c/mo\u003e\u003cmn\u003e1\u003c/mn\u003e\u003cmo\u003e,\u003c/mo\u003e\u003cmn\u003e1\u003c/mn\u003e\u003cmo stretchy\u003d\u0026quot;false\u0026quot;\u003e]\u003c/mo\u003e\u003c/math\u003e\" role\u003d\"presentation\" style\u003d\"position: relative;\"\u003e\u003cnobr aria-hidden\u003d\"true\"\u003e\u003cspan class\u003d\"math\" id\u003d\"MathJax-Span-77\" style\u003d\"width: 8.813em; display: inline-block;\"\u003e\u003cspan style\u003d\"display: inline-block; position: relative; width: 7.324em; height: 0px; font-size: 120%;\"\u003e\u003cspan style\u003d\"position: absolute; clip: rect(1.253em, 1007.21em, 2.622em, -999.997em); top: -2.199em; left: 0em;\"\u003e\u003cspan class\u003d\"mrow\" id\u003d\"MathJax-Span-78\"\u003e\u003cspan class\u003d\"mo\" id\u003d\"MathJax-Span-79\" style\u003d\"font-family: MathJax_Main;\"\u003e[\u003c/span\u003e\u003cspan class\u003d\"mn\" id\u003d\"MathJax-Span-80\" style\u003d\"font-family: MathJax_Main;\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"mo\" id\u003d\"MathJax-Span-81\" style\u003d\"font-family: MathJax_Main;\"\u003e,\u003c/span\u003e\u003cspan class\u003d\"mn\" id\u003d\"MathJax-Span-82\" style\u003d\"font-family: MathJax_Main; padding-left: 0.182em;\"\u003e5\u003c/span\u003e\u003cspan class\u003d\"mo\" id\u003d\"MathJax-Span-83\" style\u003d\"font-family: MathJax_Main;\"\u003e,\u003c/span\u003e\u003cspan class\u003d\"mn\" id\u003d\"MathJax-Span-84\" style\u003d\"font-family: MathJax_Main; padding-left: 0.182em;\"\u003e5\u003c/span\u003e\u003cspan class\u003d\"mo\" id\u003d\"MathJax-Span-85\" style\u003d\"font-family: MathJax_Main;\"\u003e,\u003c/span\u003e\u003cspan class\u003d\"mn\" id\u003d\"MathJax-Span-86\" style\u003d\"font-family: MathJax_Main; padding-left: 0.182em;\"\u003e3\u003c/span\u003e\u003cspan class\u003d\"mo\" id\u003d\"MathJax-Span-87\" style\u003d\"font-family: MathJax_Main;\"\u003e,\u003c/span\u003e\u003cspan class\u003d\"mn\" id\u003d\"MathJax-Span-88\" style\u003d\"font-family: MathJax_Main; padding-left: 0.182em;\"\u003e10\u003c/span\u003e\u003cspan class\u003d\"mo\" id\u003d\"MathJax-Span-89\" style\u003d\"font-family: MathJax_Main;\"\u003e,\u003c/span\u003e\u003cspan class\u003d\"mn\" id\u003d\"MathJax-Span-90\" style\u003d\"font-family: MathJax_Main; padding-left: 0.182em;\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"mo\" id\u003d\"MathJax-Span-91\" style\u003d\"font-family: MathJax_Main;\"\u003e,\u003c/span\u003e\u003cspan class\u003d\"mn\" id\u003d\"MathJax-Span-92\" style\u003d\"font-family: MathJax_Main; padding-left: 0.182em;\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"mo\" id\u003d\"MathJax-Span-93\" style\u003d\"font-family: MathJax_Main;\"\u003e]\u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"display: inline-block; width: 0px; height: 2.205em;\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"display: inline-block; overflow: hidden; vertical-align: -0.354em; border-left: 0px solid; width: 0px; height: 1.361em;\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/nobr\u003e\u003cspan class\u003d\"MJX_Assistive_MathML\" role\u003d\"presentation\"\u003e\u003cmath xmlns\u003d\"http://www.w3.org/1998/Math/MathML\"\u003e\u003cmo stretchy\u003d\"false\"\u003e[\u003c/mo\u003e\u003cmn\u003e1\u003c/mn\u003e\u003cmo\u003e,\u003c/mo\u003e\u003cmn\u003e5\u003c/mn\u003e\u003cmo\u003e,\u003c/mo\u003e\u003cmn\u003e5\u003c/mn\u003e\u003cmo\u003e,\u003c/mo\u003e\u003cmn\u003e3\u003c/mn\u003e\u003cmo\u003e,\u003c/mo\u003e\u003cmn\u003e10\u003c/mn\u003e\u003cmo\u003e,\u003c/mo\u003e\u003cmn\u003e1\u003c/mn\u003e\u003cmo\u003e,\u003c/mo\u003e\u003cmn\u003e1\u003c/mn\u003e\u003cmo stretchy\u003d\"false\"\u003e]\u003c/mo\u003e\u003c/math\u003e\u003c/span\u003e\u003c/span\u003e\u003cscript type\u003d\"math/tex\" id\u003d\"MathJax-Element-11\"\u003e[1, 5, 5, 3, 10, 1, 1]\u003c/script\u003e. На позициях со второй по пятую значения увеличились, значит ответ для этой перестановки\u0026nbsp;— 4.\u003c/p\u003e\u003cp\u003eВо втором тесте при любой перестановке ни на одной позиции элемент не может стать больше, значит, ответ\u0026nbsp;— 0.\u003c/p\u003e\u003c/div\u003e"}}]}