You are ordered by the king to analyze the financial report of your country.
There are N days in a year, and the report consists of exactly N integers. Each integer represents the incomes or the outgoings of the day. The king is interested about some consecutive days (possibly empty) no more than a year, such that the value of total incomes minus total outgoings during the interval is maximized. Note that the intervals that starts from the current year and ends at the next year should also be considered, provided the length of the interval is less than or equal to N. It is assumed that the same day of different years have the same amount of incomes or outgoings.
Each test case begins with a line consists of an integer N (N ≤ 105), denoting the number of days in a year. The following line contains N integers ai (|ai| ≤ 100), representing the incomes or the outgoings of the i-th day in a year.
The input is terminated by N = 0.
Output an integer in a line for each test case, representing the maximum possible value.