Алиса и Боб играют в игру. На доске написано \(n\) (\(n\) четное) целых чисел \(x_1, x_2, \ldots, x_n\). Также дано целое число \(k\) и целое число score, которое изначально равно \(0\). Игра длится \(\frac{n}{2}\) ходов, в которых последовательно происходят следующие события:
- Алиса выбирает целое число с доски и стирает его. Назовем выбранное Алисой число \(a\).
- Боб выбирает целое число с доски и стирает его. Назовем выбранное Бобом число \(b\).
- Если \(a+b=k\), добавляем \(1\) к score.
Алиса играет, чтобы минимизировать score, в то время как Боб играет, чтобы максимизировать score. Предполагая, что оба игрока используют оптимальные стратегии, каков будет score после окончания игры?
Выходные данные
Для каждого набора входных данных выведите score, если оба игрока играют оптимально.
Примечание
В первом наборе входных данных один из возможных сценариев игры выглядит следующим образом:
- Алиса выбирает \(1\), а Боб выбирает \(3\). Счет увеличивается, так как \(1+3=4\). Теперь на доске остаются два целых числа \(2\) и \(2\).
- Алиса и Боб оба выбирают \(2\). Счет увеличивается, так как \(2+2=4\).
- Игра заканчивается, так как на доске больше нет целых чисел.
В третьем наборе входных данных невозможно, чтобы сумма выбранных Алиской и Бобом целых чисел была равна \(1\), поэтому мы отвечаем \(0\).
Обратите внимание, что это всего лишь пример того, как может проходить игра для демонстрационных целей. Это может не быть самыми оптимальными стратегиями Алисы или Боба.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 4
1 2 3 2
8 15
1 2 3 4 5 6 7 8
6 1
1 1 1 1 1 1
16 9
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3
|
2
1
0
4
|