주식

홍준이는 요즘 주식에 푹 빠졌다. 앞날을 내다보는 눈이 뛰어나서 날마다의 주가를 예상하면 언제나 그대로 맞는다. 홍준이는 하루에 다음 세 가지 중 하나를 한다.

1. 주식을 한 주 산다.
2. 가지고 있는 주식을 원하는 만큼 판다.
3. 아무것도 하지 않는다.

앞날의 주가를 모두 알아도 어떻게 사고팔아야 이익이 가장 큰지는 별개의 문제다. 날마다의 주가가 주어질 때 홍준이가 얻을 수 있는 최대 이익을 구하라.

예를 들어 날이 3일이고 주가가 10, 7, 6이면 값이 계속 떨어지므로 최대 이익은 0이다. 주가가 3, 5, 9이면 첫 이틀에 한 주씩 사고 마지막 날에 모두 팔아서 이익 10을 얻는다.

첫 줄에 테스트케이스의 수 $T$가 주어진다. 각 테스트케이스의 첫 줄에는 날의 수 $N$($2 \le N \le 10^6$)이 주어지고, 둘째 줄에는 날짜 순서대로 $N$개의 주가가 공백으로 구분되어 주어진다. 주가는 $10\,000$ 이하의 자연수다.

각 테스트케이스마다 최대 이익을 한 줄에 하나씩 출력한다. 답은 부호 있는 64비트 정수로 나타낼 수 있다.