Codeforces Round 693 (Div. 3) |
---|
Закончено |
Во время своих новогодних каникул Алиса и Боб играют в следующую игру, используя массив a из n целых чисел:
Если в массиве не осталось чисел, то игра заканчивается. Побеждает тот игрок, результат которого больше. Если результаты игроков равны, то объявляется ничья.
Например, если n=4 и a=[5,2,7,3], то игра могла пройти следующим образом (существуют и другие варианты):
Вам интересно, кто победит если оба игрока будут играть оптимально. Обратите внимание, что в массиве могут быть повторяющиеся числа.
В первой строке находится целое число t (1≤t≤104) — количество наборов входных данных. Далее следуют t наборов входных данных.
В первой строке каждого набора содержится целое число n (1≤n≤2⋅105) — количество элементов в массиве a.
В следующей строке находится n целых чисел a1,a2,…,an (1≤ai≤109) — массив a, с помощью которого проводится игра.
Гарантируется, что сумма n по всем наборам входных данных не превосходит 2⋅105.
Для каждого набора входных данных в отдельной строке выведите:
4 4 5 2 7 3 3 3 2 1 4 2 2 2 2 2 7 8
Bob Tie Alice Alice
Название |
---|