#include<fstream>
using namespace std;
ifstream f("ssm.in");
ofstream g("ssm.out");
int n,i,maxi,x,sum,pi,pf,p;
int main()
{
f>>n>>x;
sum=x;p=1;maxi=-2000000000;
for(i=2;i<=n;i++)
{
f>>x;
if(sum>=0)sum+=x;
else{ sum=x; p=i; }
if(maxi<sum){maxi=sum;pi=p;pf=i;}
}
g<<maxi<<" "<<pi<<" "<<pf;
return 0;
}
//#include<fstream>
//using namespace std;
//ifstream fi("elmaj.in");
//ofstream fo("elmaj.out");
//int maj,k,t,n,i,a[1000003];
//int main()
//{
//
// fi>>n;
// for(i=1; i<=n; i++)
// fi>>a[i];
// maj=a[1];
// k=1;
// for(i=2; i<=n; i++)
// if(a[i]==maj)k++;
// else
// {
// k--;
// if(k==-1){maj=a[i];k=1;}
// }
// for(i=1; i<=n; i++)
// if(a[i]==maj)t++;
// if(t>n/2) fo<<maj<<" "<<t;
// else fo<<-1;
// return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream fi("defrag.in");
//ofstream fo("defrag.out");
//int n,v,t,i,j,s,p,P,z,a[103][363],b[806],k;
//int main()
//{
//
//fi>>v>>p>>s>>P;
//for(t=1;t<=P;t++){fi>>i>>j;a[i][j]=1;}
//if(v==1){
// for(i=1;i<=p;i++){
// k=0;
// for(j=1;j<=s;j++)k+=a[i][j];
// if(k==0)z++;
// }
// fo<<z<<'\n';
//}
//if(v==2){
// for(i=1;i<=p;i++){
// for(j=1;j<=s;j++)b[j]=b[j+s]=a[i][j];
// int q,lung=0,su,mini=10000;
// for(t=1;t<=s;t++) //lung = cati de 1 consecutivi are solutia
// lung+=b[t];
// for(t=1;t<=s;t++)
// if(b[t]==1&&b[t-1]==0) //se incepe din primul 1 (011111)
// { //numar cati de 1 are secv. de lungime "lung" si diferenta trebuie completata
// for(su=0,q=t;q<=t+lung-1;q++)su+=b[q];
// if(mini>lung-su)mini=lung-su;
// }
// if(lung==0)fo<<0<<" ";//cazul cand totul este 0
// else fo<<mini<<" ";
// }
//}
//return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream fi("submultimi.in");
//ofstream fo("submultimi.out");
//int n,sol[20],i,k;
//int main()
//{
//
//fi>>n;
//while(sol[n+1]==0)
// {
// sol[1]++;k=1;
// while(sol[k]>1)
// {
// sol[k]=0; sol[k+1]++; k++;
// }
// for(i=1;i<=n;i++)
// if(sol[i]==1) fo<<i<<" ";
// fo<<'\n';
// }
//return 0;
//}
//#include<fstream>//varianta cu generare 0,1,2
//using namespace std;
//ifstream fi("submult.in");
//ofstream fo("submult.out");
//int ssol,n,sol[20],a[20],b[20],smaxi,i,k,s1,s2,nrsol;
//int main()
//{
//n=10;
//for(i=1;i<=n;i++)fi>>a[i];
//nrsol=0;
//while(sol[n+1]==0)
// {
// sol[1]++;k=1;
// while(sol[k]>2)
// {
// sol[k]=0;
// sol[k+1]++;
// k++;
// }
// s1=s2=0;
// for(i=1;i<=n;i++)
// {if(sol[i]==1)s1+=a[i];//1 pt.el din prima multime
// if(sol[i]==2)s2+=a[i];//2 pt.el din prima multime
// }
// if(s1==s2 and s1!=0 ){
// nrsol++;
// if(s1>smaxi){
// smaxi=s1;
// for(i=1;i<=10;i++)b[i]=sol[i];//salvam suma maxima
// }
// }
// }
//fo<< nrsol/2<<" "<<smaxi<<'\n';
//for(i=1;i<=n;i++)
// if(b[i]==1)fo<<a[i]<<" ";
//fo<<'\n';
//for(i=1;i<=n;i++)
// if(b[i]==2)fo<<a[i]<<" ";
//return 0;
//}
//#include <fstream> //backtraking iterativ
//using namespace std;
//ifstream fi("submult.in");
//ofstream fo("submult.out");
//int i,j,n,ok,k,maxi;
//int a[100],b[100],c[100];
//int main()
//{n=10;
// for(i=1;i<=10;i++)fi>>b[i];
// i=1;
// while(i>0){
// if(i==n+1){ //daca am ajuns la solutie o afisam
// int s1=0;
// for(j=1;j<=10;j++)
// if(a[j]==1)s1+=b[j];
// int s2=0;
// for(j=1;j<=10;j++)
// if(a[j]==2)s2+=b[j];
// if(s1==s2){
// k++;
// if(maxi<s1){
// maxi=s1;
// for(j=1;j<=10;j++) c[j]=a[j];
// }
// }
// i--; //revenire
// }
// else //daca nu am ajuns la solutie
// if(a[i]<3){
// a[i]++; //daca se poate se creste valoarea lui a[i]
// //se verifica solitia partiala
// ok=1;
// if(ok==1) i++; //daca sol. partiala e valida se continua
// }
// else {a[i]=0;i--;}//daca nu se poate creste valoarea lui a[i] se revine
// }
// fo<<(k-1)/2<<" "<<maxi<<'\n';
// for(j=1;j<=10;j++)
// if(c[j]==1)fo<<b[j]<<" ";
//fo<<'\n';
//for(j=1;j<=10;j++)
// if(c[j]==2)fo<<b[j]<<" ";
// return 0;
//}
//#include <fstream>
//#include<cstring>
//using namespace std;
//ifstream fi ("comp.in");
//ofstream fo ("comp.out");
//char s[260];
//int s1,s2,n,i,j,k,x,t,semn,m,sol[1001];
//int main()
//{
// fi>>n;fi.get();
// for (i=1;i<=n;i++)
// {
// s1=0;s2=0;
// fi.getline(s,260);
// semn=2;
// m=strlen(s);
// for (j=0;j<m;j++)
// {if ( s[j]=='>') semn=1;
// if ( s[j]=='<') t++;
// }
// s1=0;s2=0;x=0;k=1;
// for (j=0;j<m;j++)
// if(k==1)
// {
// if (s[j]>='0' and s[j]<='9') x=x*10+s[j]-'0';
// if (s[j]=='u') {s1+=x*1;x=0;}
// if (s[j]=='z') {s1+=x*10;x=0;}
// if (s[j]=='s') {s1+=x*100;x=0;}
// if (s[j]=='m') {s1+=x*1000;x=0;}
// if (s[j]=='>' or s[j]=='<') k=2;
// }
// else
// {
// if (s[j]>='0' and s[j]<='9') x=x*10+s[j]-'0';
// if (s[j]=='u') {s2+=x*1;x=0;}
// if (s[j]=='z') {s2+=x*10;x=0;}
// if (s[j]=='s') {s2+=x*100;x=0;}
// if (s[j]=='m') {s2+=x*1000;x=0;}
// }
// if(semn==1)
// if(s1>s2) sol[i]=1;
// else sol[i]=0;
// if(semn==2)
// if(s1<s2) sol[i]=1;
// else sol[i]=0;
// }
// fo<<t<<'\n';
// for (i=1;i<=n;i++) fo<<sol[i]<<'\n';
// return 0;
//}
//#include <fstream>
//#include<cstring>
//#define M 480003
//using namespace std;
//ifstream fi("paritate.in");
//ofstream fo("paritate.out");
//char a[M];
//int k,j,i,n,s,bitp,ok,x,term;
//int main()
//{
// fi.getline(a,M);
// n=strlen(a);
// ok=1;
// for(i=0; i<n; i=i+8)
// {
// s=0;
// bitp=a[i];
// for(j=1; j<=7; j++)s+=a[i+j]-'0';
// if((s+bitp)%2==1)ok=0;
// }
// if(ok==1)
// {
// fo<<"DA"<<'\n';
// for(i=0; i<n; i=i+8)
// {
// x=0;term=1;
// for(j=7; j>=1; j--){
// x+=(a[i+j]-'0')*term;
// term=term*2;
// }
// if(x==10)fo<<'\n';
// else fo<<(char)x;
// }
// }
// if(ok==0){
// fo<<"NU"<<'\n';
// for(i=0; i<n; i=i+8)
// {
// s=0;
// bitp=a[i];
// for(j=1; j<=7; j++)s+=a[i+j]-'0';
// if((s+bitp)%2==1)fo<<k<<" ";
// k++;
// }
// }
// // fo<<'\n';
// return 0;
// }
//#include <fstream>
//using namespace std;
//ifstream fi("bool.in");
//ofstream fo("bool.out");
//char s[10003];
//int i;
//int Val[100];
//bool expresie();
//bool termen(){ //termen=(expresie) sau termen=NOT A sau termen=A
// bool rez;
// if(s[i]==' ')i++;
// else
// if(s[i]=='('){
// i++; //paranteza (
// rez=expresie();
// i++; //paranteza )
// }
// else
// if(s[i]=='N' and s[i+1]=='O' and s[i+2]=='T') {i+=3;rez=not(expresie());}
// else
// if(s[i]>='A' and s[i]<='Z'){rez=Val[s[i]-64];i++;}
// return rez;
//}
//bool factor(){ //factor=termen and termen and termen.....
// bool rez=termen();
// if (s[i]==' ')i++;
// else
// while(s[i]=='A' and s[i+1]=='N' and s[i+2]=='D')
// { i+=3; rez =rez and termen(); }
// return rez;
//}
//bool expresie(){ //expresie =factor or factor or factor.....
// bool rez=factor();
// if (s[i]==' ')i++;
// else
// while(s[i]=='O' and s[i+1]=='R')
// { i+=2; rez= rez or factor(); }
// return rez;
//}
//int main(){
// fi.get(s,1003);
// //for(i=1;i<=30;i++)Val[i]=0;
// fo<<expresie()<<'\n';
// return 0;
//}
//#include <iostream>
//#include <fstream>
//#include <cstring>
//using namespace std;
//
//ifstream in("bool.in");
//ofstream out("bool.out");
//
//const int MAXN = 1000;
//
//char s[MAXN+1], *p;
//int N;
//bool state[MAXN+1];
//
//bool evalueaza();
//bool termen();
//bool factor();
//
//void readData()
//{
// in.getline(s,MAXN);
// in>>N;
// for(int i = 0; i <= 27; i++)
// state[ i ] = false;
// for(int i = 1; i <= N; i++)
// {
// char x;
// in>>x;
// p = s;
// state[ x - 'A' ] = !state[ x - 'A' ];
// out<<evalueaza();
// }
//}
//
//bool evalueaza()
//{
// bool r = termen();
//
// while( *p == 'O' && *(p + 1) == 'R' )
// {
// p+=3;
// bool f = termen();
// r = r | f;
// }
//
// return r;
//}
//
//bool termen()
//{
// bool r = factor();
//
// while( *p == 'A' && *(p + 1) == 'N' )
// {
// p+=4;
// bool t = factor();
// r = r & t;
// }
//
// return r;
//}
//
//bool factor()
//{
// bool r;
//
//
// if( *p == '(' )
// {
// p++;
// r = evalueaza();
// p++;
// }
// else
// if( *p == 'N' && *( p + 1 ) == 'O' )
// {
// p +=4;
// r = !factor();
// }
// else
// {
// if( *p == 'T' && *(p + 1) == 'R' )
// {
// r = true;
// p += 5;
// }
// else
// if( *p == 'F' && *(p + 1) == 'A' )
// {
// r = false;
// p += 6;
// }
// else
// {
// r = state[ *p - 'A' ];
// p+=2;
// }
// }
//
// return r;
//}
//
//
//int main()
//{
// readData();
//
// //evalueaza();
// return 0;
//}
//#include <fstream>
//using namespace std;
//ifstream fi("evaluare.in");
//ofstream fo("evaluare.out");
//char s[100003];
//int i;
//int expresie();
//int termen(){ //termen=(expresie) sau termen=213
// int rez=0;
// if(s[i]=='('){
// i++; //paranteza (
// rez=expresie();
// i++; //paranteza )
// }
// else while(s[i]>='0' && s[i]<='9'){ rez=rez*10+s[i]-'0'; i++; }
// return rez;
//}
//int factor(){ //factor=termen*termen/termen*termen/termen.....
// int rez=termen();
// while(s[i]=='*' || s[i]=='/')
// if(s[i]=='*'){ i++; rez*=termen(); }
// else{ i++; rez/=termen(); }
// return rez;
//}
//int expresie(){ //expresie =factor+factor-factor+factor-factor+.....
// int rez=factor();
// while(s[i]=='+' || s[i]=='-')
// if(s[i]=='+'){ i++; rez+=factor(); }
// else{ i++; rez-=factor(); }
// return rez;
//}
//int main(){
// fi>>s;
// fo<<expresie()<<'\n';
// return 0;
//}
//#include <fstream>
//using namespace std;
//ifstream fi("evaluare.in");
//ofstream fo("evaluare.out");
//char s[100003];
//int i;
//int expresie();
//int termen(){ //termen=(expresie) sau termen=213
// int rez=0;
// if(s[i]=='('){
// i++; //paranteza (
// rez=expresie();
// i++; //paranteza )
// }
// else while(s[i]>='0' && s[i]<='9'){ rez=rez*10+s[i]-'0'; i++; }
// return rez;
//}
//int factor(){ //factor=termen*termen/termen*termen/termen.....
// int rez=termen();
// while(s[i]=='*' || s[i]=='/')
// if(s[i]=='*'){ i++; rez*=termen(); }
// else{ i++; rez/=termen(); }
// return rez;
//}
//int expresie(){ //expresie =factor+factor-factor+factor-factor+.....
// int rez=factor();
// while(s[i]=='+' || s[i]=='-')
// if(s[i]=='+'){ i++; rez+=factor(); }
// else{ i++; rez-=factor(); }
// return rez;
//}
//int main(){
// fi>>s;
// fo<<expresie()<<'\n';
// return 0;
//}
//#include <fstream>
//using namespace std;
//ifstream fi("evaluare.in");
//ofstream fo("evaluare.out");
//char s[100003];
//int i;
//int expresie();
//int termen(){ //termen=(expresie) sau termen=213
// int rez=0;
// if(s[i]=='('){
// i++; //paranteza (
// rez=expresie();
// i++; //paranteza )
// }
// else while(s[i]>='0' && s[i]<='9'){ rez=rez*10+s[i]-'0'; i++; }
// return rez;
//}
//int factor(){ //factor=termen*termen/termen*termen/termen.....
// int rez=termen();
// while(s[i]=='*' || s[i]=='/')
// if(s[i]=='*'){ i++; rez*=termen(); }
// else{ i++; rez/=termen(); }
// return rez;
//}
//int expresie(){ //expresie =factor+factor-factor+factor-factor+.....
// int rez=factor();
// while(s[i]=='+' || s[i]=='-')
// if(s[i]=='+'){ i++; rez+=factor(); }
// else{ i++; rez-=factor(); }
// return rez;
//}
//int main(){
// fi>>s;
// fo<<expresie()<<'\n';
// return 0;
//}
//#include <fstream>//var I 100p
//#include <cmath>//cu ciur si desc. in factori +super optimizari
//using namespace std;
//ifstream fi("nrdiv.in");
//ofstream fo("nrdiv.out");
//bool prim[4000000];
//int nrd,p,i,j,nb,n,nrmax,zz;
//long long q,t,x,maxi,a[60],b[700000];
//int main()
//{
// fi>>n;
// for (i=1; i<=n; i++)
// fi>>a[i];
// for (i=1; i<=n; i++)
// if (a[i]>maxi) maxi=a[i];
//
// //Ciur Eratostene
// nrmax=(int )sqrt((double)maxi);
// for(t=2; t<=nrmax ;t++)
// if (prim[t]==0)
// for(q=t*t; q<=nrmax; q=q+t) prim[q]=1;
//
// //constructie vector d numere prime
// for (t=2; t<=nrmax; t++)
// if (prim[t]==0) b[++nb]=t;
// b[++nb]=(int)1e9;
// for (i=1; i<=n; i++)
// {
// x=a[i];
// nrd=1;
// for(j=1;b[j]*b[j]<=x;j++){
// p=0;
// while(x%b[j]==0)
// p++,x/=b[j];
// nrd*=(p+1);
// }
// if(x!=1)nrd*=2;
// fo<<nrd<<'\n';
// }
// return 0;
//}
//#include <fstream>//10p varianta ca desc in factori primi!!!
//#include <cmath>//timp depasit
//using namespace std;
//ifstream fi("nrdiv.in");
//ofstream fo("nrdiv.out");
//bool prim[4000000];
//long long x,a[60],b[700000];
//long long nrmax, d,n,i,p,k,j,maxi,nb,nrd;
//int main()
//{
// fi>>n;
// for (i=1; i<=n; i++)
// fi>>a[i];
//
// for (i=1; i<=n; i++)
// {
// nrd=1;
// x=a[i];
// d=2;
// while (x!=1)
// {
// p=0;
// while (x%d==0)
// {
// x=x/d;
// p++;
// }
// nrd=nrd*(p+1);
// d++;
// if(nrd==1&&d*d>x){nrd=2;break;}//optimizare pentru numere prime
// }
// fo<<nrd<<'\n';
// }
// return 0;
//}
//#include <fstream>//40p nu se incadreaza in timp
//#include <cmath>//cu ciur si desc. in factori +optimizari
//using namespace std;
//ifstream fi("nrdiv.in");
//ofstream fo("nrdiv.out");
//bool prim[4000000];
//long long x,maxi,a[60],b[700000];
//long long nrmax, n,i,p,k,j,nb,nrd,zz;
//int main()
//{
// fi>>n;
// for (i=1; i<=n; i++)
// fi>>a[i];
// for (i=1; i<=n; i++)
// if (a[i]>maxi) maxi=a[i];
//
// //Ciur Eratostene
// nrmax=(long long )sqrt((double)maxi);
// for(int i=2; i<=nrmax ;i++)
// if (prim[i]==0)
// for(int j=i*2; j<=nrmax; j=j+i) prim[j]=1;
//
// //constructie vector d numere prime
// for (i=2; i<=nrmax; i++)
// if (prim[i]==0) b[++nb]=i;
//
// for (i=1; i<=n; i++)
// {
// x=a[i];
// zz=(long long )sqrt((double)x);nrd=1;
// for(j=1; x!=1 && j<=nb && b[j]<=zz;j++){
// p=0;
// while(x%b[j]==0)
// p++,x/=b[j];
// nrd*=(p+1);
// }
// if(x!=1)nrd*=2;
// fo<<nrd<<'\n';
// }
// return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream f("petrol.in");
//ofstream g("petrol.out");
//int n,eu,du,i,j;
//double maxi,e[101],d[101];
//int main()
//{
// f>>n>>eu>>du;
// for(i=1; i<=n; i++)
// f>>e[i]>>d[i];
// for(i=1; i<=n; i++)
// {
// e[i]=eu/e[i];
// d[i]=du/d[i];
// }
// if(n!=1)
// {for(i=1; i<=n; i++)
// for(j=1; j<=n; j++)
// if(i!=j)
// maxi=max(maxi,e[i]+d[j]);
// g<<maxi;
// }
// else g<<max(e[1],d[1]);
//
// return 0;
//}
//#include <cstdio>//varianata IV 100p
//using namespace std;
//int palme,n,k,i,x,fr[100001];
//int main(){
// freopen("carti1.in","r",stdin);
// freopen("carti1.out","w",stdout);
// scanf("%d",&n); //citire modificata
// for(i=1;i<=n;i++)
// { scanf("%d",&x); //citire modificata
// if(fr[x-1]==1){fr[x-1]=0;fr[x]=1;}
// else fr[x]=1;
// }
// for(i=1;i<=n;i++)
// if(fr[i]>0)palme++;
//
// printf("%d\n",palme-1);//afisare modificata
// return 0;
//}
//#include <fstream>//varianata III 50p timpul de citire !!!!!
//using namespace std;
//ifstream f("carti1.in");
//ofstream g("carti1.out");
//int palme,n,k,i,x,fr[100001];
//int main(){
// f>>n;
// for(i=1;i<=n;i++)
// {
// f>>x;
// if(fr[x-1]==1){fr[x-1]=0;fr[x]=1;}
// else fr[x]=1;
// }
// for(i=1;i<=n;i++)
// if(fr[i]>0)palme++;
// g<<palme-1;
// return 0;
//}
//#include <fstream>//varianata II 50p timpul de citire !!!!!
//using namespace std;
//ifstream f("carti1.in");
//ofstream g("carti1.out");
//int palme,n,k,i,x,fr[100001];
//int main(){
// f>>n;
// for(i=1;i<=n;i++) //se ia in ordine fiecare element
// {
// f>>x; //se ia in ordine fiecare element!!!!
// if(fr[x-1]==1) //daca este deja pus precedentul sau(x-1) pe 1
// {fr[x-1]=0;fr[x]=1;} //atunci precedentul sa pune pe 0
// //si cel curent (x) se pune pe 1
// else fr[x]=1; //altfel cel curent (x) se pune pe 1
// }
// for(i=1;i<=n;i++)
// if(fr[i]>0)palme++; //solutia va fi numarul de elemente de 1 din care scadem 1
//
// g<<palme-1;
// return 0;
//}
//#include <fstream>//varianata I 30p timpul de citire si rezolvare!!!
//using namespace std;
//ifstream f("carti1.in");
//ofstream g("carti1.out");
//int palme,n,k,i,maxi,a[100001];
//int main(){
// f>>n;
// for(i=1;i<=n;i++)f>>a[i];
// k=1;i=1;palme=0;
// while(1==1){
// if(a[i]==k)k++;
// i++;
// if(k==n+1)break;
// if(i==n+1){i=1;palme++;}
// }
// g<<palme;
// return 0;
//}
//#include <fstream>
//using namespace std;
//ifstream f("ciur.in");
//ofstream g("ciur.out");
//bool prim[2006000];
//int sol=0;
//int n=0;
//int main()
//{
// f>>n;
//
//for(int i=2;i<=n;++i)
// if (prim[i]==0)
// for(int j=i*2;j<=n;j+=i)
// prim[j]=1;
//
//for(int i=2;i<=n;++i)
// if (prim[i]==0){//g<<i<<" ";
// ++sol;
// }
//g<<sol;
//return 0;
//}
////vezi cmmmc 2010 ONI IX
//#include <iostream>
//#include<cmath>
//using namespace std;
//int nrsol;
//int pp,i,j,r,m,n,x;
//int a[1001],p[50000],b[20000];
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
// //ciur Eratostene
// r=sqrt(2000000004);
// for(i=2;i<=r;i++)
// if(p[i]==0)
// for(j=2*i;j<=r;j+=i)p[j]=1;
// for(i=2;i<=r;i++)
// if(p[i]==0)b[++m]=i;
// // for(i=1;i<=m;i++)cout<<b[i]<<" ";
// for(i=1;i<=n;i++){
// x=a[i];nrsol=1;
// j=1;
// while(x!=1 and x>=b[j] and j<=m)//avem x, numerele din ciur nu depasesc x,
// { //nu s-a terminat numerele din ciur
// pp=0;
// while(x%b[j]==0){pp++;x=x/b[j];}
// nrsol*=(2*pp+1);
// j++;
// }
// if(a[i]==1)nrsol=1; //caz particular x==1
// else if(a[i]==x)nrsol=3;//caz particular numar prim
// else if(x!=1)nrsol=nrsol*3;//caz cand avem numar cu factor prim>sqrt(x)
// //x=2*13 sqrt(26)=5.1 deci nu-l gaseste pe 13 !!
// //daca ramane ceva in x dupa desc. atunci ramane
// //doar un numar prim!!!! si atunci *3
// cout<<nrsol<<" ";
// }
// return 0;
//}
//#include <iostream>//bac V25 SIII pr4
//#include<fstream>
//using namespace std;
//float a,b;
//float n;
//ifstream f("bac.txt");
//int cmmdc(int a,int b){
// int r;
// do{
// r=a%b;
// a=b;
// b=r;
// }while(r);
// return a;
//}
//int main()
//{
// f>>n;
// a=n;b=1;
// while((int)a!=a){a=a*10;b=b*10;}
// cout<<a/cmmdc(a,b)<<" "<<b/cmmdc(a,b);
// return 0;
//}
//#include <iostream>//bac V23 SIII pr4
//#include<fstream>
//using namespace std;
//int a[1001],b[1001],j,i,n;
//bool se_inter;
//ifstream f("bac.txt");
//bool intersectie(int a,int b,int c,int d){
// if(b<c or d<a) return false;
// else return true;
//}
//int main()
//{
// f>>n;
// for(i=1;i<=n;i++)
// f>>a[i]>>b[i];
// for(i=1;i<=n;i++){
// se_inter=false;
// for(j=1;j<=n;j++)
// if(i!=j)
// if(intersectie(a[i],b[i],a[j],b[j])==true)se_inter=true;
// if(se_inter==false)cout<<a[i]<<" "<<b[i]<<endl;
// }
// return 0;
//}
//#include <iostream>
//#include<cstring>
//using namespace std;
//char a[100],b[100];
//char ch,e;
//int n,i,nr,k,m;
//int main()
//{
// cin.get(a,100);
// n=strlen(a);
// k=0;
// for(i=0;i<n;i++)
// if(a[i]!=' ')k++;
// else {m=max(m,k);k=0;}
//
// m=max(m,k);
// cout<<m;
// return 0;
//}
//#include <iostream>//Babes 2012
//#include <cmath>
//using namespace std;
//int a[100],n,i;
//void citire(int a[100],int &n){
// int x;
// while(cin>>x)
// if(x)a[++n]=x;
// else break;
//}
//void afisare(int a[100],int n){
//int i;
//for(i=1;i<=n;i++)
// cout<<a[i]<<" ";
//}
//bool asemenea(int x,int y){
// int i;
// int frx[10],fry[10];
// for(i=0;i<=9;i++)frx[i]=fry[i]=0;
// while(x){frx[x%10]=1;x=x/10;}
// while(y){fry[y%10]=1;y=y/10;}
// for(i=0;i<=9;i++)
// if(frx[i]!=fry[i])return false;
// return true;
//}
//void eliminare_subsir(int a[100],int &n,int p1,int p2){
//int i,j;
//j=p1;
//for(i=p2+1;i<=n;i++)
// a[j++]=a[i];
//n-=p2-p1+1;
//}
//void eliminare_secv_asemenea(int a[100],int &n){
//int i,j;
// i=1;
// while(i<=n){
// j=i;
// while(asemenea(a[j],a[j+1]))j++;
// if(i!=j)eliminare_subsir(a,n,i,j);
// else i++;
// }
//}
//int main()
//{
// citire(a,n);
// eliminare_secv_asemenea(a,n);
// afisare(a,n);
//
// return 0;
//}
//#include <iostream>
//#include <cmath>
//using namespace std;
//int i,n,s,S,mini,maxi,maxd,k,x,a,b,d,y;
//int main()
//{cin>>n;
//while(n%2==0)n=n/2;
//S=0;
//for(d=1;d<=n/2;d=d+2)
// if(n%d==0)S+=d;
//if(n%2==1) S+=n;
//cout<<S;
//return 0;
//}
//#include <iostream>//100p
//using namespace std;
//int x,y,d,z,t,a,b,r;
//int main()
//{cin>>x>>y;
//a=x;b=y;
//do{
// r=x%y;
// x=y;
// y=r;
//}while(r);
//for(d=1;d<=x;d++)
//if(a%d==0 and b%d==0)cout<<d<<" ";
//return 0;
//}
//#include <iostream>//90p
//using namespace std;
//int x,y,d,z,t;
//int main()
//{cin>>x>>y;
//z=min(x,y);
//t=z/2;
//for(d=1;d<=t;d++)
//if(x%d==0 and y%d==0)
//cout<<d<<" ";
//if(x%z==0 and y%z==0)cout<<z;
//return 0;
//}
//#include <iostream>//90p
//using namespace std;
//int x,y,d,mini;
//int main()
//{cin>>x>>y;
//mini=min(x,y);
//for(d=1;d<=mini;d++)
//if(x%d==0 and y%d==0)
//cout<<d<<" ";
//return 0;
//}
//
//#include <fstream>
//using namespace std;
//ifstream fi("zone.in");
//ofstream fo("zone.out");
//int a[303],i,j,n,k;
//bool gasit1,gasit2;
//int main()
//{
//fi>>n;
//for(i=1;i<=3*n;i++)fi>>a[i];
//gasit1=false;
//for(i=1;i<=n;i++)
// if(a[i]%2==0){gasit1=true;break;}
//gasit2=false;
//for(j=3*n;j>=2*n+1;j--)
// if(a[j]%2==1){gasit2=true;break;}
//if(gasit1==true and gasit2==true)swap(a[i],a[j]);
//for(i=1;i<=3*n;i++)fo<<a[i]<<" ";
// return 0;
//}
//#include <iostream>
//using namespace std;
//int a[200][200],i,j,v,vv,n,k;
//int main()
//{
// cin>>n;
// k=(n+1)/2;
// for(v=1;v<=k;v++)
// {
// a[v][k]=v;
// vv=v;i=v;
// j=k+1;
// while(vv){a[i][j]=--vv;j++;}
// vv=v;i=v;
// j=k-1;
// while(vv){a[i][j]=--vv;j--;}
// }
// for(i=1;i<=n;i++){
// for(j=1;j<=n;j++)
// if(i<=n/2)a[n-i+1][j]=a[i][j];
// }
// for(i=1;i<=n;i++){
// for(j=1;j<=n;j++)cout<<a[i][j]<<" ";
// cout<<endl;
// }
// return 0;
//
//}
////#include <iostream>
////using namespace std;
////int x1,y1,x2,y2;
////int main()
////{
//// cin>>x1>>y1>>x2>>y2;
//// if(x1==x2)cout<<"verticala";
//// else if(y1==y2)cout<<"orizontala";
//// else cout<<"oblica";
//// return 0;
////
////}
//#include <fstream>
//using namespace std;
//ifstream fi("spectacole.in");
//ofstream fo("spectacole.out");
// int n, i,j, x[101], y[101], k, ales;
// int main()
//{
// fi>>n;
// for(i=1;i<=n;i++) fi>>x[i]>>y[i];
// for(i=1;i<=n;i++)
// for(j=i+1;j<=n;j++)
// if(y[i]>y[j]){
// swap(x[i], x[j]);
// swap(y[i], y[j]);
// }
// k=1;
// ales=y[1];
// //fo<<x[1]<<" "<<y[1]<<endl;
// for(i=2;i<=n;i++)
// if(ales<=x[i]){
// k++;
// // fo<<x[i]<<" "<<y[i]<<endl;
// ales=y[i];
// }
// fo<<k;
// return 0;
//}
//
//#include <iostream>
//#include<cstring>
//using namespace std;
//char s[100];
//char c;
//int i,j,p,n; //mare frig saci =>mare frig sai
//int main()
//{
// cin.get(s,100);
// n=strlen(s);
// for(i=n-1;i>=0;i--)
// if(s[i]!=' ' and s[i]!='a' and s[i]!='e' and
// s[i]!='i' and s[i]!='o' and s[i]!='u' )
// {p=i;break; }
// cout<<p<<" ";
// strcpy(s+p,s+p+1);
// cout<<s;
//// cout<<"dati propozitie";
//// cin.get(a,100);
//// //a)
//// cout<<"lungimea propozitiei:"<<strlen(a)<<endl;
//// // b)
//// for(i=0;i<strlen(a);i++)
//// if(a[i]=='a' or a[i]=='A')k++;
//// cout<<"numarul de litere de a este:"<<k<<endl;
//// //c)
//// cout<<"propozitia fara litera 'c' este:";
//// for(i=0;i<strlen(a);i++)
//// if(a[i]!='c' and a[i]!='C')cout<<a[i];
//// cout<<endl;
//// //d)
////// for(i=0;i<strlen(a);i++)
////// if(a[i]>='a' and a[i]<='z')a[i]=a[i]-32;
////// cout<<a<<endl;
//// //e)
////// for(i=0;i<strlen(a);i++)
////// if(a[i]>='a' and a[i]<='z')a[i]=a[i]-32;
////// else
////// if(a[i]>='A' and a[i]<='Z') a[i]=a[i]+32;
////// cout<<a<<endl;
//// //f)
//// int voc=0,con=0;
//// for(i=0;i<strlen(a);i++)
//// if((a[i]>='a' and a[i]<='z')or(a[i]>='A' and a[i]<='Z'))
//// if(a[i]=='a' or a[i]=='e' or a[i]=='i' or a[i]=='o' or a[i]=='u' or
//// a[i]=='A' or a[i]=='E' or a[i]=='I' or a[i]=='O' or a[i]=='U' )voc++;
//// else con++;
//// cout<<"numar vocale si consoane:"<<voc<<" "<<con<<endl;
//
// return 0;
//}
//
//#include <iostream>
//#include<cstring>
//using namespace std;
//char a[100],b[100];
//char ch,e;
//int main()
//{
// cin>>a; //citire sir(cuvânt) pâna la spațiu
// cout<<a<<" "<<strlen(a)<<" "<<a[0];
//
// cin.get(a,100); //citire sir(propozitie) cu cin.get( , ) var I
// cout<<a;
//
//// cin.get(a,100,'m'); //citire sir(propozitie) cu cin.get( , , ) var II
//// cout<<a;
//
// return 0;
//}
//#include <fstream>//var I
//using namespace std;
//ifstream f("munte3.in");
//ofstream g("munte3.out");
// int a[101],b[101],fr[101],sk,s,i,n,k,j,p;
// int main()
//{
// f>>n;
// for(i=1;i<=n;i++)
// f>>a[i];
// for(i=2;i<n;i++)
// if(a[i-1]<a[i] and a[i]>a[i+1])k++;
// g<<k<<endl;
// do{
// for(i=1;i<=n;i++)fr[i]=0;
// k=0;
// for(i=2;i<n;i++)
// if(a[i-1]<a[i] and a[i]>a[i+1]){k++;fr[i]=1;}
// if(k==0)break;
// else
// {
// sk+=k;
// p=0;
// for(i=1;i<=n;i++)
// if(fr[i]==0)b[++p]=a[i];//{p++;b[p]=a[i];}
// for(i=1;i<=p;i++) a[i]=b[i]; n=p;
// }
// }while(1);
// g<<sk<<endl<<n;
// return 0;
//}
//#include <fstream>//var II
//using namespace std;
//ifstream f("meteo1.in");
//ofstream g("meteo1.out");
// int a[1001],s,i,n,k,j,maxi,pi,pf;
// int main()
//{
// f>>n;
// for(i=1;i<=n;i++)
// f>>a[i];
// k=1;
// for(i=1;i<n;i++)
// if((a[i]<0 and a[i+1]>=0) or (a[i]>=0 and a[i+1]<0))k++;
// else {
// if(k>=maxi){maxi=k;pi=i-k+1;pf=i;}
// k=1;
// }
// if(k>=maxi){maxi=k;pi=i-k+1;pf=i;}
// if(maxi>=2){
// g<<maxi<<endl;
// for(i=pi;i<=pf;i++)g<<a[i]<<" ";
// }
// else g<<0;
// return 0;
//}
//#include <fstream>//var I
//using namespace std;
//ifstream f("meteo1.in");
//ofstream g("meteo1.out");
// int a[1001],s,i,n,k,j,maxi,pi,pf;
// int main()
//{
// f>>n;
// for(i=1;i<=n;i++)
// f>>a[i];
// for(i=1;i<=n;i++)
// {
// k=1;
// for(j=i;j<n;j++)
// if((a[j]<0 and a[j+1]>=0)or (a[j]>=0 and a[j+1]<0))
// k++;
// else break;
// if(k>=maxi){maxi=k;pi=i;pf=j;}
// }
// if(maxi>=2){
// g<<maxi<<endl;
// for(i=pi;i<=pf;i++)g<<a[i]<<" ";
// }
// else g<<0;
// return 0;
//}
//#include <fstream>
//#define NMax 1001
//using namespace std;
//ifstream fi("eoliene.in");
//ofstream fo("eoliene.out");
// int n, i,j, x[NMax], y[NMax],d[NMax],l[NMax],k, ales;
// int main()
//{
// fi>>n;
// for(i=1;i<=n;i++) fi>>d[i];
// for(i=1;i<=n;i++) fi>>l[i];
// for(i=1;i<=n;i++) {x[i]=d[i]-l[i];y[i]=d[i]+l[i];}
// for(i=1;i<=n;i++)
// for(j=i+1;j<=n;j++)
// if(y[i]>y[j]){
// swap(x[i], x[j]);
// swap(y[i], y[j]);
// }
// k=1;
// ales=y[1];
// for(i=2;i<=n;i++)
// if(ales<x[i]){
// k++;
// ales=y[i];
// }
// fo<<n-k;
// return 0;
//}
//
//#include <iostream>
//#include<cstring>
//using namespace std;
//char a[100],b[100];
//char ch,e,*p;
//int strlena(char a[100]){
//int i=0;
// while(a[i]!='\0')i++;
// return i;
// //return strlen(a);
//}
//int main()
//{
// cin.get(a,100); //citire sir(propozitie) cu cin.get( , , ) var II
// for(int i=0;i<strlen(a);i++)
// a[i]=a[i+1];
// cout<<a;;
//
//
//return 0;
//}
//#include <iostream>
//using namespace std;
//void detnr(int x,int a[100])
//{
// int n=0;
// while(x!=0)
// {
// a[++n]=x%10;
// x=x/10;
// }
//}
//int palindrom(int a[100],int n)
//{
// int j=n,i=1;
// while(i<=j)
// {
// if(a[i]!=a[j]) return 0;
// i++;j--;
// }
// return 1;
//}
//
//
//void tiparire(int a[100][100],int n)
//{
// int i,j;
// for(i=1;i<=n;i++)
// {
// for(j=1;j<=n;j++)
// cout<<a[i][j]<<" ";
// cout<<endl;
// }
//}
//int n,i,j,a[100][100];
//int main()
//{
//
// return 0;
//}
//#include <iostream>
//using namespace std;
//int prim(int x)
//{
// int d,k=0;
// for(d=1;d<=x;d++)
// if(x%d==0) k++;
// if(k==2) return 1;
// else return 0;
//}
//int mprim(int m)
//{
// int k,p;
// p=0;
// k=1;
// while(p!=m)
// {
// k++;
// if(prim(k)==1)
// p++;
// }
// return k;
//}
//void tiparire(int a[100][100],int n)
//{
// int i,j;
// for(i=1;i<=n;i++)
// {
// for(j=1;j<=n;j++)
// cout<<a[i][j]<<" ";
// cout<<endl;
// }
//}
//int n,i,j,a[100][100];
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)
// if(i==j) a[i][j]=0;
// else if(i>j) a[i][j]=i;
// else if(i<j) a[i][j]=mprim(i);
// tiparire(a,n);
// return 0;
//}
//
//// www.pbinfo.ro
//#include <fstream>
//using namespace std;
//ifstream fi("maxsim.in");
//ofstream fo("maxsim.out");
//int maxi,n,i,p1,p2,a[1001];
//bool prim;
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)fi>>a[i];
// for(i=1;i<=n/2;i++)
// if(maxi<a[i]+a[n-i+1]){maxi=a[i]+a[n-i+1];p1=i;p2=n-i+1;}
// fo <<maxi<<" "<<p1<<" "<<p2;
// return 0;
//}
//
//// nrapprime www.pbinfo.ro stergeti el prime
//#include <fstream>//100p
//#include<cmath>
//using namespace std;
//ifstream fi("nrapprime.in");
//ofstream fo("nrapprime.out");
//int n,i,j,t, x,d,rad,a[1001];
//bool prim;
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)fi>>a[i];
// for(i=1;i<=n;i++)
// {
// x=a[i];
// if(x==0 or x==1)prim=false;
// if(x==2)prim=true;
// if(x>2){
// prim=true;
// rad=sqrt(x);
// for(d=2;d<=rad;d++)
// if(x%d==0){prim=false;break;}
// }
// if(prim) t++;
// }
//
// fo <<t;
// return 0;
//}
//// nraparitii www.pbinfo.ro
//#include <fstream>
//using namespace std;
//ifstream fi("nraparitii.in");
//ofstream fo("nraparitii.out");
//int k,i,n,maxi,a[1001];
//
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)fi>>a[i];
// for(i=1;i<=n;i++)
// if(a[i]==a[n])k++;
// fo<<k;
// return 0;
//}
//// minmax www.pbinfo.ro
//#include <fstream>
//using namespace std;
//ifstream fi("minmax.in");
//ofstream fo("minmax.out");
//int mini,i,n,maxi,a[1001];
//
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)fi>>a[i];
// mini=a[1];
// for(i=1;i<=n;i++)
// if(a[i]<mini)mini=a[i];
// for(i=1;i<=n;i++)
// if(a[i]>maxi)maxi=a[i];
// fo<<mini<<" "<<maxi;
// return 0;
//}
//// majoritar www.pbinfo.ro
//#include <iostream>//100p
//using namespace std;
//int k,majoritar,i,n,t,a[100001];
//
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
// majoritar=a[1];
// for(i=1;i<=n;i++)
// {if(a[i]==majoritar)k++;
// else k--;
// if(k==0){majoritar=a[i];k=1;}
// }
// for(i=1;i<=n;i++)
// if(a[i]==majoritar)t++;
// if(t>n/2)cout<<"DA "<<majoritar;
// else cout<<"NU";
// return 0;
//}
//// inserareDupa www.pbinfo.ro
//#include <iostream>//100p
//using namespace std;
//int i,n,t,a[1001],b[1001];
//
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
// for(i=1;i<=n;i++)
// {
// b[++t]=a[i];
// if(a[i]%2==0)b[++t]=a[i]*2;
// }
// for(i=1;i<=t;i++)
// cout<<b[i]<<" ";
// return 0;
//}
//// numarMunte www.pbinfo.ro stergeti el prime
//#include <iostream>//100p
//using namespace std;
//int c,n,i,j,t, x,d,k,a[1001];
//bool prim;
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
// for(i=1;i<=n;i++)
// {
// x=a[i];k=0;t=0;
// c=x%10;x=x/10;
// while(c<x%10&&x>0){c=x%10;x=x/10;k++;}
// while(c>x%10&&x>0){c=x%10;x=x/10;t++;}
// if(t&&k&&x==0)cout<<1<<endl;
// else cout<<0<<endl;
// }
// return 0;
//}
//// sterge www.pbinfo.ro stergeti el prime
//#include <iostream>//100p
//#include<cmath>
//using namespace std;
//int n,i,j,t, x,d,rad,a[1001];
//bool prim;
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
// for(i=1;i<=n;i++)
// {
// x=a[i];
// if(x==0 or x==1)prim=false;
// if(x==2)prim=true;
// if(x>2){
// prim=true;
// rad=sqrt(x);
// for(d=2;d<=rad;d++)
// if(x%d==0){prim=false;break;}
// }
// if(prim) {for(j=i;j<n;j++)a[j]=a[j+1];n--;i--;}
// }
// for(i=1;i<=n;i++)
// cout <<a[i]<<" ";
// return 0;
//}
////PermCirc www.pbinfo.ro
//#include <iostream>
//using namespace std;
//int t,p,s,n,i,x,k,a[1001];
//int main()
//{
// cin>>n;
// for(i=1; i<=n; i++)cin>>a[i];
// for(t=1; t<=n; t++)
// {
// for(i=1; i<=n; i++) cout<<a[i]<<" ";
// cout<<endl;
// x=a[1];
// for(i=1; i<n; i++)
// a[i]=a[i+1];
// a[n]=x;
// }
// return 0;
//}
////inserareInainte www.pbinfo.ro
//#include <iostream>
//#include<cmath>
//using namespace std;
//int m,maxi,cnt,n,i,x,k,j,a[101][1001];
//int main()
//{
// cin>>m>>n;
// for(i=1;i<=m;i++)
// for(j=1;j<=n;j++)
// cin>>a[i][j];
//
// for(i=1;i<=m;i++)
// for(j=1;j<=n;j++)
// if(maxi<a[i][j])maxi=a[i][j];
//
// for(i=1;i<=m;i++){
// k=0;
// for(j=1;j<=n;j++)
// if(maxi==a[i][j])k++;
// if(k>0)cnt++;
// }
// cout<<maxi<<" "<<cnt;
// return 0;
//}
////inserareInainte www.pbinfo.ro
//#include <iostream>
//#include<cmath>
//using namespace std;
//int p,s,n,i,x,k,j,a[1001];
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
//
// for(i=1;i<=n;i++)
// if(sqrt(a[i])==(int)sqrt(a[i]))
// {
// for(j=n;j>=i;j--)a[j+1]=a[j];
// a[i]=sqrt(a[i]);
// n++;
// i++;
// }
// for(i=1;i<=n;i++)
// cout<<a[i]<<" ";
// return 0;
//}
////inserare www.pbinfo.ro
//#include <iostream>
//using namespace std;
//int p,s,n,i,x,k,a[1001];
//int main()
//{
// cin>>n>>x>>p;
// for(i=1;i<=n;i++)cin>>a[i];
//
// for(i=n;i>=p;i--)
// a[i+1]=a[i];
// a[p]=x;
// n++;
// for(i=1;i<=n;i++)
// cout<<a[i]<<" ";
// return 0;
//}
////inlociure www.pbinfo.ro
//#include <iostream>
//using namespace std;
//int med,s,n,i,j,k,a[1001];
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
//
// for(i=1;i<=n;i++)
// if(a[i]!=0){s+=a[i];k++;}
// med=s/k;
// for(i=1;i<=n;i++)
// if(a[i]==0)a[i]=med;;
// for(i=1;i<=n;i++)
// cout<<a[i]<<" ";
// return 0;
//}
//// numarare3 www.pbinfo.ro
//#include <iostream>
//using namespace std;
//int n,i,j,k;
//int x,y,a[1001];
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
// for(i=1;i<=n;i++)
// {
// x=a[i];y=a[n];
// while(x!=y)
// if(x>y)x=x-y;
// else y=y-x;
// if(x==1)k++;
// }
// cout <<k;
// return 0;
//}
//// constr1 www.pbinfo.ro
//#include <iostream>
//using namespace std;
//int s,n,i,j,t,a[1001],b[1001];
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
// for(i=1;i<=n;i++)s+=a[i];
//
// for(i=1;i<=n;i++)b[i]=s-a[i];
//
// for(i=1;i<=n;i++) cout <<b[i]<<" ";
// return 0;
//}
//// constr2 www.pbinfo.ro af el prime in ordine inversa
//#include <iostream>//100p
//#include<cmath>
//using namespace std;
//int n,i,j,t, x,d,rad,a[1001],b[1001];
//bool prim;
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
// for(i=1;i<=n;i++)
// {
// x=a[i];
// if(x==0 or x==1)prim=false;
// if(x==2)prim=true;
// if(x>2){
// prim=true;
// rad=sqrt(x);
// for(d=2;d<=rad;d++)
// if(x%d==0){prim=false;break;}
// }
// if(prim) b[++t]=x;
// }
// for(i=t;i>=1;i--)
// cout <<b[i]<<" ";
// return 0;
//}
//// constr2 www.pbinfo.ro af el prime in ordine inversa
//#include <iostream>//60p
//#include<cmath>
//using namespace std;
//int k,n,i,j,t, x,d,rad,a[1001],b[1001];
//bool prim;
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
// for(i=1;i<=n;i++)
// {
// x=a[i];k=0;
// for(d=2;d<=x/2;d++)
// if(x%d==0)k++;
// if(k==0) b[++t]=x;
// }
// for(i=t;i>=1;i--)
// cout <<b[i]<<" ";
// return 0;
//}
//// constr www.pbinfo.ro
//#include <iostream>
//using namespace std;
//int n,i,j,k;
//int x,s,y,a[1001],b[1001];
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
// for(i=1;i<=n;i++)
// {
// x=a[i];s=0;
// while(x){
// s+=x%10;
// x=x/10;
// }
// b[i]=a[i]%s;
// }
// for(i=1;i<=n;i++)
// cout <<b[i]<<" ";
// return 0;
//}
//// numarare5 www.pbinfo.ro
//#include <iostream>
//using namespace std;
//int n,i,j,k,sx,sy;
//int x,y,a[1001];
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
// for(i=1;i<=n;i++)
// for(j=i+1;j<=n;j++)
// {
// x=a[i];sx=0;
// while(x){
// sx+=x%10;
// x=x/10;
// }
// y=a[j];sy=0;
// while(y){
// sy+=y%10;
// y=y/10;
// }
// if(sx==sy)k++;
// }
// cout <<k;
// return 0;
//}
//// numarare3 www.pbinfo.ro
//#include <iostream>
//using namespace std;
//int n,i,j,k;
//int x,y,a[1001];
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
// i=1;j=n;
// while(i<j)
// {
// x=a[i];y=a[j];
// while(x!=y)
// if(x>y)x=x-y;
// else y=y-x;
// if(x==1)k++;
// i++;j--;
// }
// cout <<k;
// return 0;
//}
//// numarare7 www.pbinfo.ro
//#include <iostream>
//using namespace std;
//int s,n,i,j,k;
//float x,y,a[1001];
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
// x=a[1];y=a[n];
// if(x>y)swap(x,y);
// for(i=1;i<=n;i++)
// if(a[i]<x or a[i]>y)k++;
// cout <<k;
// return 0;
//}
////numarare2 www.pbinfo.ro
//#include <iostream>
//using namespace std;
//int s,n,i,j,k,a[1001];
//float med;
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
//
// for(i=1;i<=n;i++)
// s+=a[i];
// med=(float)s/n;
// for(i=1;i<=n;i++)
// if(a[i]>med)k++;
// cout <<k;
// return 0;
//}
////suma2 www.pbinfo.ro (suma de la primul par si ultimul par)
//#include <iostream>
//using namespace std;
//int s,n,i,j,ip,iq,mini,maxi,a[1001];
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
//
// for(i=1;i<=n;i++)
// if(a[i]%2==0){ip=i;break;}
// for(i=n;i>=1;i--)
// if(a[i]%2==0){iq=i;break;}
//
// if(ip==0)cout<<"NU EXISTA";
// else { for(i=ip;i<=iq;i++)s+=a[i];cout << s;}
// return 0;
//}
////numere6 www.pbinfo.ro (cate el. sunt = maxi-mini)
//#include <iostream>
//using namespace std;
//int k,dif,n,i,j,imin,imax,mini,maxi,a[1001];
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
//
// mini=a[1];
// for(i=1;i<=n;i++)
// if(a[i]<mini)mini=a[i];
//
// maxi=a[1];
// for(i=1;i<=n;i++)
// if(a[i]>maxi)maxi=a[i];
//
// dif=maxi-mini;
// for(i=1;i<=n;i++)
// if(a[i]==dif)k++;
// cout << k;
// return 0;
//}
////pozminmax www.pbinfo.ro
//#include <iostream>
//using namespace std;
//int n,i,j,imin,imax,mini,maxi,a[1001];
//int main()
//{
// cin>>n;
// for(i=1;i<=n;i++)cin>>a[i];
//
// mini=a[1];imin=1;
// for(i=1;i<=n;i++)
// if(a[i]<mini){mini=a[i];imin=i;}
//
// maxi=a[1];imax=1;
// for(i=1;i<=n;i++)
// if(a[i]>maxi){maxi=a[i];imax=i;}
//
// cout << imin<<" " << imax;
// return 0;
//}
bodnariuc danut danutbod