DevuLand is a very strange place. There are n villages in it. Some of the villages are occupied by dinosaurs while the remaining ones by villagers.
	You are given the information of DevuLand 
	by an array D of size n. If D[i] is non-negative, it means that there are D[i] villagers in that village. 
	Otherwise, it means that are -D[i] 
	dinosaurs in that village.

	It is also guaranteed that total number of villagers in DevuLand is equal to total number of dinosaurs.

Once dinosaurs got very hungry and started eating villagers. Frightened villagers gathered immediately and met their Sarpanch Deviji. Deviji, being a very daring and negotiable person, met to the head
of dinosaurs. Soon both parties called a truce. It was decided that the villagers will provide laddus to 
the dinosaurs. So everyday, each villager will take exactly one laddu to one of the dinosaurs in such a way that no dinosaur remains hungry (note that this is possible because number of villagers is the same as the number of dinosaurs).

Actually, carrying laddus is a quite a tough job. Villagers have to use a bullock cart for that. It takes one unit of grass a bullock to 
carry a cart with 1 laddu for 1 kilometre. Laddus used to be very heavy in DevuLand, so a bullock cart can not carry more than one laddu.

It is also given distance between village indexed i and j is |j - i| (the absolute value) kilometres.

Now villagers sat down and found a strategy to feed laddus to dinosaurs so that they need to buy the least amount of grass from the nearby market. 
They are not very good in 
calculations, please find out what is the minimum number of units of grass they need to buy.

-----Input-----

First line of the input contains an integer T denoting number of test cases.

For each test case, there are two lines. 

First line contains a single integer denoting n: number of villages. 

Second line contains n space separated integers denoting the array D.

-----Output-----

For each test case, print a single line containing the integer corresponding to answer of the problem.

-----Constraints-----

-  1 ≤ T ≤ 10^5 
-  1 ≤ n ≤ 10^5 
-  -10^4 ≤ D[i] ≤ 10^4 
-  Sum of n over all the test cases will be ≤ 10^6 
-  It is guaranteed that sum of D[i] is zero for a single test case which ensures that there are equal number of villagers and dinosaurs. 

-----Example-----
Input:
3
2
5 -5
2
-5 5
3
1 2 -3
Output:
5
5
4

-----Explanation-----
Example case 1. Each villager in village 1, need to walk 1 km to reach to the dinosaur in 2nd village.
Example case 2. Each villager in village 2, need to walk 1 km to reach to the dinosaur 1st village.
Example case 3. Each villager in village 1, need to walk 2 km to reach to the dinosaur in 3rd village whereas Each villager in village 2, 
need to walk 1 km to reach to the dinosaur in 3rd village.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Starter code:

Solutions:
import sys
t = int(sys.stdin.readline())
for i in range(0, t):
	n = int(sys.stdin.readline())
	D = sys.stdin.readline().split()
	c = 0
	k = 0
	for i in range(0, n):
		c += int(D[i])
		k += abs(c)
	print(k)


from _collections import deque

def solve(A):
	lP = deque([i for i in range(len(A)) if A[i] > 0])
	lN = deque([i for i in range(len(A)) if A[i] < 0])
	s = 0
	for iN in lN:
		while A[iN] < 0:
			iP = lP[0]
			v = A[iP]
			if v >= abs(A[iN]):
				s += abs(iN - iP) * abs(A[iN])
				A[iP] -= abs(A[iN])
				A[iN] = 0
			else:
				s += abs(iN - iP) * abs(A[iP])
				A[iN] += A[iP]
				lP.popleft()
	return s
T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	print(solve(A))


t = int(input())
for i in range(t):
	n = int(input())
	d = list(map(int, input().split()))
	l1 = []
	l2 = []
	for j in range(n):
		l = []
		l.append(d[j])
		l.append(j)
		if d[j] >= 0:
			l1.append(l)
		else:
			l2.append(l)
	n1 = len(l1)
	n2 = len(l2)
	a = 0
	b = 0
	ans = 0
	while a < n1 and b < n2:
		if -l2[b][0] > l1[a][0]:
			l2[b][0] = l2[b][0] + l1[a][0]
			ans = ans + l1[a][0] * abs(l2[b][1] - l1[a][1])
			a = a + 1
		elif -l2[b][0] == l1[a][0]:
			ans = ans + l1[a][0] * abs(l2[b][1] - l1[a][1])
			b = b + 1
			a = a + 1
		elif -l2[b][0] < l1[a][0]:
			l1[a][0] = l1[a][0] + l2[b][0]
			ans = ans + -l2[b][0] * abs(l2[b][1] - l1[a][1])
			b = b + 1
	print(ans)


import sys
__author__ = 'zumzoom'
t = int(sys.stdin.readline().split()[0])
for _ in range(t):
	n = int(sys.stdin.readline().split()[0])
	A = [int(i) for i in sys.stdin.readline().split()]
	cur_dino = -1
	cur_vill = -1
	for i in range(n):
		if A[i] > 0:
			cur_vill = i
			break
	for i in range(n):
		if A[i] < 0:
			cur_dino = i
			break
	ans = 0
	while cur_vill < n and cur_dino < n:
		while A[cur_vill] > 0 > A[cur_dino]:
			cur_min = min(A[cur_vill], -A[cur_dino])
			A[cur_vill] -= cur_min
			A[cur_dino] += cur_min
			ans += cur_min * abs(cur_vill - cur_dino)
		while cur_vill < n and A[cur_vill] <= 0:
			cur_vill += 1
		while cur_dino < n and A[cur_dino] >= 0:
			cur_dino += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	d = list(map(int, input().split()))
	ans = 0
	c = 0
	for j in d:
		ans += abs(c)
		c += j
	print(ans)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	(ans, tmp) = (0, 0)
	for i in range(n - 1):
		tmp += l[i]
		ans += abs(tmp)
	print(ans)


def read_inps():
	n = int(input())
	arr = input().split(' ')
	arr = [int(i) for i in arr]
	return (n, arr)

def solve_for(n, arr):
	grass = 0
	lad = 0
	j = 1
	lad = arr[0]
	while j < n:
		grass = grass + abs(lad)
		lad = lad + arr[j]
		j += 1
	grass = grass + abs(lad)
	return grass
T = int(input())
for i in range(T):
	ins = read_inps()
	print(solve_for(ins[0], ins[1]))


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	ans = 0
	xd = 0
	for p in x:
		ans += abs(xd)
		xd += p
	print(ans)


cases = int(input())
for i in range(cases):
	vilnos = int(input())
	vills = [int(j) for j in input().split(' ')]
	grass = abs(vills[0])
	for j in range(1, vilnos):
		vills[j] += vills[j - 1]
		grass += abs(vills[j])
	print(grass)


for _ in range(int(input())):
	N = int(input())
	st = input().split()
	r = 0
	d = 0
	for x in st:
		r += abs(d)
		d += int(x)
	print(r)


import sys
import math
from time import time
from itertools import permutations, combinations
import collections
import functools
from fractions import gcd, Fraction
import string
import operator
import bisect

class timed(object):

	def __init__(self, func):
		self.func = func

	def __call__(self, *args):
		t1 = time()
		ret = self.func(*args)
		dif_time = time() - t1
		print('%s: returned %s in %f seconds' % (self.func.__name__, ret, dif_time))
		return ret

def comp(f1, f2, *args):
	t1 = time()
	r1 = f1(*args) if f1 is not None else None
	t2 = time()
	r2 = f2(*args) if f2 is not None else None
	t3 = time()
	res = '%5s: %s in %f\n%5s: %s in %f' % (f1.__name__ if f1 is not None else None, r1, t2 - t1, f2.__name__ if f2 is not None else None, r2, t3 - t2)
	if r1 != r2:
		dr = '!! DIFFERENT RESULTS !!'
		res = dr + '\n' + res + '\n' + dr
	print(res)

def alg2(vill):
	length = len(vill)
	moves = 0
	cur = 0
	for i in range(length):
		cur += vill[i]
		moves += abs(cur)
	return moves

def alg(vill):
	length = len(vill)
	moves = 0
	for i in range(length):
		while vill[i] != 0:
			for j in range(i + 1, length):
				dist = j - i
				if vill[i] < 0 and vill[j] > 0:
					if -vill[i] <= vill[j]:
						vill[j] += vill[i]
						moves -= vill[i] * dist
						vill[i] = 0
					else:
						vill[i] += vill[j]
						moves += vill[j] * dist
						vill[j] = 0
				if vill[i] > 0 and vill[j] < 0:
					if -vill[j] <= vill[i]:
						vill[i] += vill[j]
						moves -= vill[j] * dist
						vill[j] = 0
					else:
						vill[j] += vill[i]
						moves += vill[i] * dist
						vill[i] = 0
	return moves

def main():
	data = sys.stdin
	nb = int(data.readline())
	for icase in range(nb):
		nb_villages = int(data.readline().strip())
		vill = list(map(int, data.readline().split()))
		res = alg2(vill)
		print(res)
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	curr = 0
	ans = 0
	for x in a:
		curr += x
		ans += abs(curr)
	print(ans)


t = int(input())
for z in range(t):
	n = int(input())
	numbers = list(map(int, input().split()))
	total = 0
	answer = 0
	for i in range(n):
		total += numbers[i]
		answer += abs(total)
	print(answer)


T = int(input())
for t in range(T):
	N = int(input())
	D = list(map(int, input().split()))
	(v, d) = (0, 0)
	while v < N and D[v] <= 0:
		v += 1
	while d < N and D[d] >= 0:
		d += 1
	ans = 0
	while v < N:
		assert d < N
		if D[v] + D[d] > 0:
			D[v] += D[d]
			ans += abs((v - d) * D[d])
			D[d] = 0
			d += 1
		elif D[v] + D[d] < 0:
			D[d] += D[v]
			ans += abs(v - d) * D[v]
			D[v] = 0
			v += 1
		else:
			ans += D[v] * abs(v - d)
			(D[v], D[d]) = (0, 0)
			v += 1
			d += 1
		while v < N and D[v] <= 0:
			v += 1
		while d < N and D[d] >= 0:
			d += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	d = list(map(int, input().split()))
	tot = ans = 0
	for i in range(0, n - 1):
		tot += d[i]
		ans += abs(tot)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	grass = 0
	for i in range(n):
		if arr[i] != 0:
			grass += abs(arr[i])
			arr[i + 1] += arr[i]
			arr[i] = 0
	print(grass)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	hu = 0
	di = 0
	tot = 0
	while hu < n and di < n:
		while arr[hu] <= 0:
			hu += 1
			if hu >= n:
				break
		while arr[di] >= 0:
			di += 1
			if di >= n:
				break
		if hu >= n or di >= n:
			break
		if arr[hu] <= abs(arr[di]):
			tot += arr[hu] * abs(hu - di)
			arr[di] += arr[hu]
			arr[hu] = 0
		else:
			tot += abs(arr[di]) * abs(hu - di)
			arr[hu] += arr[di]
			arr[di] = 0
	print(tot)


for t in range(int(input())):
	nn = int(input())
	a = list(map(int, input().split()))
	p = []
	lp = 0
	n = []
	ln = 0
	for i in range(nn):
		if a[i] < 0:
			n.append([i, -a[i]])
			ln += 1
		elif a[i] > 0:
			p.append([i, a[i]])
			lp += 1
	ans = 0
	p1 = 0
	p2 = 0
	while p1 < lp and p2 < ln:
		if p[p1][1] < n[p2][1]:
			ans += abs(p[p1][0] - n[p2][0]) * p[p1][1]
			n[p2][1] -= p[p1][1]
			p1 += 1
			continue
		elif p[p1][1] > n[p2][1]:
			ans += abs(p[p1][0] - n[p2][0]) * n[p2][1]
			p[p1][1] -= n[p2][1]
			p2 += 1
		elif p[p1][1] == n[p2][1]:
			ans += abs(p[p1][0] - n[p2][0]) * p[p1][1]
			p1 += 1
			p2 += 1
	print(ans)