적도

도시들이 한 바퀴로 늘어선 행성 적도에서, 한 방향으로 연속된 구간만 털 수 있다. 각 도시의 수익(음수면 손실)이 주어질 때 얻을 수 있는 최대 총액을 구하라. 아예 착륙하지 않아 0을 선택할 수도 있다.

첫 줄에 테스트 수 $T$가 주어진다. 각 테스트는 도시 수 $n$과 $n$개의 정수 $c_i$로 주어진다.

각 테스트마다 최대 총 수익을 한 줄에 출력한다.