Проблема лифта
На цокольном (нулевом) этаже большого университетского здания студенты ждут лифт. Обычно лифт останавливается на каждом этаже, где один или несколько студентов должны выйти, но это раздражает тех, кто хочет выйти выше. Кроме того, лифт может пропустить некоторые этажи, но это раздражает студентов, которые хотели бы выйти на одном из них.
В частности, студент раздражается на каждом этаже где останавливается лифт, пока он не доедет до своего этажа. Если лифт пропускает этаж, на котором хочет выйти студент, то студент раздражаться на этом этаже и на каждом этаже выше, вплоть до того, пока лифт не сделает свою следующую остановку (на этом этаже студент уже не раздражается), после чего студент выходит и начинает спускаться по лестнице к месту назначения.
Например, если студент хочет выйти на пятом этаже, а лифт останавливается на втором, седьмом и десятом, то студент будет раздражен на втором, пятом и шестом этажах. В целом этот студент будет раздражен на трех этажах.
При входе в лифт каждый студент нажимает кнопку, соответствующую его этажу, даже если кнопка уже была нажата кем-то другим. Таким образом, центральный процессор, управляющий лифтом, точно знает, сколько студентов хотят выйти на каждом этаже.
Вам поручено запрограммировать Центральный Процессор чтобы решить, на каких этажах следует останавливаться. Цель состоит в том, чтобы свести к минимуму общий уровень недовольства: количество этажей, на которых каждый студент раздражен, суммируется для всех учеников.
Вы можете игнорировать всех людей, которые могут (хотят) войти в лифт на любом верхнем этаже. Подъемник должен работать таким образом, чтобы каждый ученик, ожидающий его на цокольном этаже, смог либо выйти на своем этаже, либо выйти на некотором этаже и спуститься вниз по лестнице.
Входные данные
Первая строка содержит количество тестов, не большее 100. Далее для каждого теста:
первая строка содержит n (1 ≤ n ≤ 1500) - количество этажей в здании, исключая цокольный этаж.
одна строка содержит n целых чисел
s[i](0 ≤s[i]≤ 1500):s[i]равно числу студентов, которые хотят выйти на i-ом этаже.
Выходные данные
Для каждого теста вывести в отдельной строке наименьшее возможное значение общего уровня недовольства лифтом.