N个整数组成的序列a[1],a[2],a[3],…,a[n]，从中选出一个子序列（a[i],a[i+1],…a[j]），使这个子序列的和>0，并且这个和是所有和>0的子序列中最小的。

例如：4，-1，5，-2，-1，2，6，-2。-1，5，-2，-1，序列和为1，是最小的。

 

Input

第1行：整数序列的长度N（2 <= N <= 50000)第2 - N+1行：N个整数

Output

输出最小正子段和。

Input示例

84-15-2-126-2

Output示例

1 代码如下：

#include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long LL;struct node{    LL m;    int pos;} A[50005];bool cmp(const node x,const node y){    return x.m
           
            =0; j--)            {                LL tmp=A[i].m-A[i-1].m;                if(A[i].pos
            
             0) { t=min(t,tmp); break; } } } cout<
             
              <