PRLADDU : DevuLand, Dinosaurs and Laddus Легенда, описанная далее, переформулирована и упрощена переводчиком, чтобы читатель мог лучше понять условие задачи. Оригинальную легенду вы можете прочитать на странице задачи в контесте. Условие: Рассмотрим N деревень, расположенных друг за другом. Расстояние между двумя деревнями, скажем, i-ой и j-ой есть |i-j|. В каждой из деревень находятся либо люди, либо динозавры. Информация о них дана массивом D. Если D[i] >= 0, то в i-ой деревне находится D[i] людей, иначе - -D[i] динозавров. Гарантируется, что суммарное количество людей равняется суммарному количеству динозавров. Требуется каждому человеку поставить в соответствие одного динозавра так, чтобы это соответствие было взаимнооднозначным (то есть, каждому динозавру поставлен в соответствие ровно один человек и каждый человек поставлен в соответствие ровно одному динозавру), чтобы сумма расстояний между деревнями людей и поставленных им в соответствие динозавров была минимальной. Формат ввода: Первая строка содержит целое число T – количество тестовых случаев. Далее следует T описаний тестов. Первая строка каждого описания содержит целое число N – количество деревень. Вторая строка содержит N разделенных одиночными пробелами целых чисел – массив D, описывающий деревни. Формат вывода: Для каждого тестового случая выведите минимальную возможную сумму расстояний. Ограничения: • • • • • 1 <= T <= 105 1 <= N <= 105 -104 <= Di <= 104 Сумма всех N в одном тестовом файле <= 106 Сумма всех Di равна нулю в каждом тестовом случае, что гарантирует равенство количества людей и количества динозавров. Примеры тестов: Входные данные: 3 2 5 -5 2 -5 5 3 1 2 -3 1 Выходные данные: 5 5 4 Пояснение: В первом тестовом примере, каждому жителю первой деревни поставлен в соответствие динозавр из второй деревни. Во втором тестовом примере, каждому жителю второй деревни поставлен в соответствие динозавр из первой деревни. В третьем тестовом примере каждому жителю второй деревни поставлен в соответствие динозавр из третьей, и житель из первой деревни также имеет динозавра их третьей деревни поставленным себе в соответствие. Получаем сумму расстояний |2-3| + |2-3| + |1-3| = 4. 1