There is a number sequence A1,A2....An,you can select a interval [l,r] or not,all the numbers Ai(l≤i≤r) will become f(Ai).f(x)=(1890x+)mod10007.After that,the sum of n numbers should be as much as possible.What is the maximum sum?

There are multiple test cases.

First line of each case contains a single integer n.(≤n≤)

Next line contains n integers A1,A2....An.(≤Ai≤)

It's guaranteed that ∑n≤106.

For each test case,output the answer in a line.

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<math.h>

 #include<algorithm>

 #include<queue>

 #include<set>

 #include<bitset>

 #include<map>

 #include<vector>

 #include<stdlib.h>

 #include <stack>

 using namespace std;

 #define PI acos(-1.0)

 #define max(a,b) (a) > (b) ? (a) : (b)

 #define min(a,b) (a) < (b) ? (a) : (b)

 #define ll long long

 #define eps 1e-10

 #define MOD 1000000007

 #define N 100006

 #define inf 1e12

 int n;

 int a[N];

 int A[N];

 int main()

 {

    while(scanf("%d",&n)==){

       int ans=;

       for(int i=;i<n;i++){

          scanf("%d",&a[i]);

          ans+=a[i];

       }

       for(int i=;i<n;i++){

          A[i]=(a[i]*+)%-a[i];

          //printf("===%d\n",A[i]);

       }

       int ThisSum=,MaxSum=;

       for(int i=;i<n;i++){

          ThisSum+=A[i];

          if(ThisSum>MaxSum){

             MaxSum=ThisSum;

          }else if(ThisSum<){

             ThisSum=;

          }

       }

       ans+=MaxSum;

       printf("%d\n",ans);

    }

     return ;

 }