26580번 - Rain 다국어

문제

In your city, there is a shortage of drinking water so the city planner is finding more ways to trap rainwater to be used for drinking. The city has varying heights of buildings, and rainwater gets trapped between the buildings. The city planner has asked you to write a program that, given the heights of the buildings, can find the largest amount of rainwater that can get trapped between the buildings.

입력

The first line will contain a single integer n that indicates the number of data sets that follow. Each data set will consist of a single line of integers, denoting the heights of the buildings. The building height can be positive or negative.

출력

Output the total amount of rainwater that can be trapped between/above the buildings of varying height.

제한

힌트