#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int s=0,st=0,s1=0,c=0;
for(int i=0;i<n;i++)
{
if(s<a[i] && i>0)
{
st=-s+i*a[i];
s1=-1;c=-1;
}
else if(s1<a[i] && c>0)
{
st=st-s1+c*a[i];
}
if(s1==-1)
s1=0;
else
s1=s1+a[i];
s=s+a[i];c++;
}
cout<<st<<endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKCWludCB0OwoJY2luPj50OwoJd2hpbGUodC0tKQoJewoJaW50IG47CgljaW4+Pm47CglpbnQgYVtuXTsKCWZvcihpbnQgaT0wO2k8bjtpKyspCgl7CgkJY2luPj5hW2ldOwoJfQoJaW50IHM9MCxzdD0wLHMxPTAsYz0wOwoJZm9yKGludCBpPTA7aTxuO2krKykKCXsKICAgICAgCWlmKHM8YVtpXSAmJiBpPjApCiAgICAgIAl7CiAgICAgIAkJc3Q9LXMraSphW2ldOwogICAgICAJCXMxPS0xO2M9LTE7CiAgICAgIAl9CiAgICAgIAllbHNlIGlmKHMxPGFbaV0gJiYgYz4wKQogICAgICAJewogICAgICAJCXN0PXN0LXMxK2MqYVtpXTsKICAgICAgCX0KICAgICAgCWlmKHMxPT0tMSkKICAgICAgCXMxPTA7CiAgICAgIAllbHNlCiAgICAgIAlzMT1zMSthW2ldOwogICAgICAJcz1zK2FbaV07YysrOwogICAgICAJCgl9CgogICAgY291dDw8c3Q8PGVuZGw7Cn0KCXJldHVybiAwOwp9