小 A 喜欢坐地铁。地铁环线有 n个车站，依次以1,2,...n 标号。车站 i（1<=i < n)）的下一个车站是车站i+1 。特殊地，车站n 的下一个车站是车站1。 小 A 会从某个车站出发，乘坐地铁环线到某个车站结束行程，这意味着小 A 至少会经过一个车站。小 A 不会经过一个车站多次。当小 A 乘坐地铁环线经过车站i时，小 A 会获得ai 点快乐值。请你安排小 A 的行程，选择出发车站与结束车站，使得获得的快乐值总和最大

第一行，一个正整数 n。

第二行， n个整数 a1,a2,...an。

一行，一个整数，表示小 A 能获得的最大快乐值。

数据范围 对于 20% 的测试点，保证 1<=n<=200。

对于 40% 的测试点，保证 1<=n<=2000。

对于所有测试点，保证1<=n<=2 * 10^5 ，-10^9<=ai<=10^9 。