Железный дровосек и мишки Гамми
Железный дровосек и мишки Гамми
На одном из популярных интернет-ресурсов с завидной регулярностью происходит нашествие злобных мишек Гамми. Попав на ресурс, они все как один начинают по команде вожака голосовать "за" (+) или "против" (-) всех сообщений подряд. Понимая, что их проделки могут быть обнаружены, а сами они наказаны, мишки Гамми на ресурсе маскируются. Для этого каждая пара мишек Гамми создаёт виртуального пользователя и прикрепляет к нему аватар добродушного плюшевого медведя, поэтому всем пользователям кажется, что голосуют не мишки Гамми, а плюшевые медведи.
В разных сообщениях обитатели портала могут голосовать по разному, но в одном сообщении мнение всех проголосовавших одинаковое.
Железный дровосек, будучи привыкшим к определённому порядку, решил наказать проказников. Для этого ему нужно для начала определить, какой максимальной численности клика мишек Гамми находилась в наблюдаемое время на ресурсе. Помогите ему в этом.
Входные данные
В первой строке задано натуральное число t - количество тестовых случаев, не превышающее 100. Далее идёт 2t строк, где сначала в первой строке указывается количество активных новых сообщений за наблюдаемый период n (1 ≤ n ≤ 10^5), а в следующей строке - рейтинг соответствующего сообщения r_i (r_i ≤ |2·10^9|) на момент просмотра.
Выходные данные
Для каждого тестового случая выведите в отдельной строке соответствующее решение задачи в формате, указанном в примере выходных данных.
Пример
2 2 3 4 5 -7 6 12 -13 9
Case 1: 3 Case 2: 4