Вам дан массив \(a\) из \(n\) целых чисел.
Будем называть медианой массива \(q_1, q_2, \ldots, q_k\) число \(p_{\lceil \frac{k}{2} \rceil}\), где \(p\) — отсортированный по неубыванию массив \(q\). Например, медиана массива \([9, 5, 1, 2, 6]\) это \(5\), так как в отсортированном массиве \([1, 2, 5, 6, 9]\) число с индексом \(\lceil \frac{5}{2} \rceil = 3\) это \(5\), а медиана массива \([9, 2, 8, 3]\) это \(3\), так как в отсортированном массиве \([2, 3, 8, 9]\) число с индексом \(\lceil \frac{4}{2} \rceil = 2\) это \(3\).
За одно действие вам разрешается выбрать целое число \(i\) (\(1 \le i \le n\)) и увеличить \(a_i\) на \(1\).
Ваша задача найти минимальное количество действий, за которое можно увеличить медиану массива.
Обратите внимание, что в массиве \(a\) необязательно все числа различны.
Примечание
В первом наборе входных данных можно применить одну операцию к первому числу и получить массив \([3, 2, 8]\), у этого массива медиана равна \(3\), так как это число с индексом \(\lceil \frac{3}{2} \rceil = 2\) в отсортированном по неубыванию массиве \([2, 3, 8]\). У изначального массива \([2, 2, 8]\) медиана равна \(2\), так как это число с индексом \(\lceil \frac{3}{2} \rceil = 2\) в отсортированном по неубыванию массиве \([2, 2, 8]\). Таким образом медиана увеличилась (\(3 > 2\)) всего за одно действие.
В четвертом наборе входных данных можно применить по одной операции к числам с индексами \(1, 2, 3\) и получить массив \([6, 6, 6, 4, 5]\), у этого массива медиана равна \(6\), так как это число с индексом \(\lceil \frac{5}{2} \rceil = 3\) в отсортированном по неубыванию массиве \([4, 5, 6, 6, 6]\). У изначального массива \([5, 5, 5, 4, 5]\) медиана равна \(5\), так как это число с индексом \(\lceil \frac{5}{2} \rceil = 2\) в отсортированном по неубыванию массиве \([4, 5, 5, 5, 5]\). Таким образом медиана увеличилась (\(6 > 5\)) за три действия. Можно показать, что это минимальное возможное количество действий.
В пятом наборе входных данных можно применить по одной операции к числам с индексами \(1, 3\) и получить массив \([3, 1, 3, 3, 1, 4]\), у этого массива медиана равна \(3\), так как это число с индексом \(\lceil \frac{6}{2} \rceil = 3\) в отсортированном по неубыванию массиве \([1, 1, 3, 3, 3, 4]\). У изначального массива \([2, 1, 2, 3, 1, 4]\) медиана равна \(2\), так как это число с индексом \(\lceil \frac{6}{2} \rceil = 3\) в отсортированном по неубыванию массиве \([1, 1, 2, 2, 3, 4]\). Таким образом медиана увеличилась (\(3 > 2\)) за два действия. Можно показать, что это минимальное возможное количество действий.