Алиса и Боб играют в игру. Изначально есть \(n\) тортов, у \(i\)-го из них вкусность равна \(a_i\).
Алиса и Боб по очереди их едят, первой начинает Алиса:
- В свой ход Алиса выбирает и ест любой из оставшихся тортов, вкусность которого строго выше максимальной вкусности любого из съеденных ею до этого тортов. Обратите внимание, что в первый ход Алиса может съесть любой торт.
- В свой ход Боб выбирает любой из оставшихся тортов и ест его.
Игра заканчивается, когда текущий игрок не может съесть подходящий торт. Пусть \(x\) это число тортов, съеденных Алисой. Тогда Алиса хочет максимизировать \(x\), в то время как Боб хочет минимизировать \(x\).
Сколько тортов съест Алиса, если оба игрока будут выбирать торты оптимально?
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество тортов, съеденных Алисой, если оба игрока будут играть оптимально.
Примечание
В первом наборе входных данных одна возможная последовательность ходов — следующая:
- Алиса съедает торт со вкусностью \(1\). Остались торты со вкусностями \([4, 2, 3]\).
- Боб съедает торт со вкусностью \(2\). Остались торты со вкусностями \([4, 3]\).
- Алиса съедает торт со вкусностью \(3\). Остались торты со вкусностями \([4]\).
- Боб съедает торт со вкусностью \(4\). Остались торты со вкусностями \([]\).
- Так как больше тортов нет, игра на этом заканчивается.
Во втором наборе входных данных одна возможная последовательность ходов — следующая:
- Алиса съедает торт со вкусностью \(1\). Остались торты со вкусностями \([1, 1]\).
- Боб съедает торт со вкусностью \(1\). Остались торты со вкусностями \([1]\).
- Так как Алиса уже съела торт со вкусностью \(1\), она не может сделать ход, поэтому игра на этом заканчивается.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
4
1 4 2 3
3
1 1 1
5
1 4 2 3 4
4
3 4 1 4
1
1
8
4 3 2 5 6 8 3 4
7
6 1 1 3 5 3 1
11
6 11 6 8 7 5 3 11 2 3 5
17
2 6 5 3 9 1 6 2 5 6 3 2 3 9 6 1 6
|
2
1
3
2
1
3
2
4
4
|