//#include<stdio.h>
//int dp[100][100] = {};
//int sum[100][100] = {};
//int main()
//{
// int n, m, i, j, k;
// scanf("%d %d",&n, &m);
// dp[1][1] = 1;
// sum[1][1] = 1;
// for(i=1;i<=n;i++)
// {
// dp[i][i] = 1;
// sum[i][i] = 1;
// for(j=1;j<=i;j++)
// {
// dp[i][j] += sum[i-j][j];
// sum[i][j] = sum[i][j-1] + dp[i][j];
// for(k=i+1;k<=m;k++)
// {
// sum[i][k] = sum[i][i];
// }
// }
// }
// printf("%d", sum[n][m]);
//}
//#include<stdio.h>
//int dp[2000][2000] = {};
//int sum[2000][2000] = {};
//int main()
//{
// int n, m, i, j, k;
// scanf("%d %d",&n, &m);
// dp[1][1] = 1;
// sum[1][1] = 1;
// for(i=1;i<=n;i++)
// {
// dp[i][i] = 1;
// sum[i][i] = 1;
// for(j=1;j<=i;j++)
// {
// dp[i][j] += sum[i-j][j];
// sum[i][j] = (sum[i][j-1] + dp[i][j])%123456789;
// for(k=i+1;k<=m;k++)
// {
// sum[i][k] = sum[i][i];
// }
// }
// }
// printf("%d", sum[n][m]);
//}
//#include<stdio.h>
//int dp[5005][5005] = {};
//int sum[5005][5005] = {};
//int main()
//{
// int n, m, i, j, k;
// scanf("%d %d",&n, &m);
// dp[1][1] = 1;
// sum[1][1] = 1;
// for(i=1;i<=n;i++)
// {
// dp[i][i] = 1;
// sum[i][i] = 1;
// for(j=1;j<=i;j++)
// {
// dp[i][j] += sum[i-j][j];
// sum[i][j] = (sum[i][j-1] + dp[i][j])%123456789;
// }
// for(k=i+1;k<=m;k++)
// {
// sum[i][k] = sum[i][i];
// }
// }
// printf("%d", sum[n][m]);
//}
#include<stdio.h>
#define max(a,b) (((a) > (b)) ? (a) : (b))
int main()
{
int n, sum, max_sum, arr[300000] = {}, i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d", &arr[i]);
}
if sum
}