QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#125842#6627. Line Towndengtingyu19 245ms62604kbC++143.1kb2023-07-17 19:30:452023-07-17 19:32:07

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-17 19:32:07]
  • 评测
  • 测评结果:19
  • 用时:245ms
  • 内存:62604kb
  • [2023-07-17 19:30:45]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 500010
#define inf 1e15
ll n;
ll a[N];
ll xu[N],cn=0;
struct shuz{
	ll c[N];
	#define lowbit(i) (i&(-i))
	inline void update(ll x,ll y){
		for(int i=x;i<=n;i+=lowbit(i))c[i]+=y;
		return ;
	}inline ll ask(ll x){
		ll an=0;for(int i=x;i;i-=lowbit(i))an+=c[i];
		return an;
	}
}; 
vector<ll>ji[2][N],tem[2][2];
ll f[N][2];ll nw;ll siz;
inline void chuli(ll i,ll op){
	for(int j=0;j<=1;j++)for(int k=0;k<=1;k++)tem[j][k].clear(),tem[j][k].resize(ji[j][i].size());
	ll u=op^(nw&1);
	for(int g=0;g<ji[op][i].size();g++){
		ll sm1=upper_bound(ji[op^1][i].begin(),ji[op^1][i].end(),ji[op][i][g])-ji[op^1][i].begin();
		tem[op][0][g]=ji[op][i][g]-sm1-g-1;tem[op][1][g]=nw-siz-tem[op][0][g];
		tem[op][0][g]+=abs(g-sm1);
		ll p=(ji[op][i].size()-g-1);if(u!=op)p++;
		ll tt=ji[op^1][i].size()-p-sm1;if(tt<0)tt=-tt;
		tem[op][1][g]+=tt;
	}for(int g=0;g<ji[op^1][i].size();g++){
		ll sm0=upper_bound(ji[op][i].begin(),ji[op][i].end(),ji[op^1][i][g])-ji[op][i].begin();
		tem[op^1][0][g]=ji[op^1][i][g]-sm0-g-1,tem[op^1][1][g]=nw-siz-tem[op^1][0][g];
	}for(int g=1;g<ji[op][i].size();g++)tem[op][0][g]+=tem[op][0][g-1];
	for(int g=1;g<ji[op^1][i].size();g++)tem[op^1][0][g]+=tem[op^1][0][g-1];
	for(int g=ji[op][i].size()-2;g>=0;g--)tem[op][1][g]+=tem[op][1][g+1];
	for(int g=ji[op^1][i].size()-2;g>=0;g--)tem[op^1][1][g]+=tem[op^1][1][g+1];
	reverse(tem[op^1][1].begin(),tem[op^1][1].end());
	reverse(tem[op][1].begin(),tem[op][1].end());
	return ;
}
bool kz[N];
int main()
{
//	freopen("test1.in","r",stdin);
	//freopen(".in","r",stdin);
	//freopen("test1.out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;for(int i=1;i<=n;i++)cin>>a[i],xu[++cn]=abs(a[i]);
	for(int i=1;i<=n;i++)if(a[i]<0)a[i]=-a[i],kz[i]=1;
	sort(xu+1,xu+cn+1);cn=unique(xu+1,xu+cn+1)-xu-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(xu+1,xu+cn+1,a[i])-xu;
	shuz o;for(int i=1;i<=cn;i++)f[i][0]=f[i][1]=inf;
	for(int i=1;i<=n;i++){
		o.update(a[i],1);
		ll g=o.ask(a[i]);
		ji[kz[i]^(i&1)][a[i]].push_back(g);
	}f[cn+1][1]=0;f[cn+1][0]=inf;nw=n;
	for(int i=cn;i>=1;i--){
		if((ji[0][i].empty()&&ji[1][i].empty())||xu[i]==0){
			f[i][1]=f[i+1][1];f[i][0]=f[i+1][0];continue;
		}ll o=f[i+1][0],pi=f[i+1][1];siz=ji[0][i].size()+ji[1][i].size();
		chuli(i,1);//f[x][0]
		ll p=(nw&1)^1;
		for(int j=0;j<=siz;j++){
			ll las=siz-j;
			ll q1=(j+1)/2,h1=(las+p)/2,q0=j-q1,h0=las-h1;
			if(q1+h1!=ji[1][i].size()||h0+q0!=ji[0][i].size())continue;
			ll an=o+(q0==0?0:tem[0][0][q0-1])+(h0==0?0:tem[0][1][h0-1])+
			(q1==0?0:tem[1][0][q1-1])+(h1==0?0:tem[1][1][h1-1]);
			f[i][(j&1)]=min(f[i][(j&1)],an);
		}
		chuli(i,0);//f[x][1]
		p=(nw&1);
		for(int j=0;j<=siz;j++){
			ll las=siz-j;
			ll q1=j/2,h1=(las+p)/2,q0=j-q1,h0=las-h1;
			if(q1+h1!=ji[1][i].size()||h0+q0!=ji[0][i].size())continue;
			ll an=pi+(q0==0?0:tem[0][0][q0-1])+(h0==0?0:tem[0][1][h0-1])+
			(q1==0?0:tem[1][0][q1-1])+(h1==0?0:tem[1][1][h1-1]);
			f[i][(j&1)^1]=min(f[i][(j&1)^1],an);
		}
		nw-=siz;
	}ll ans=min(f[1][0],f[1][1]);
	if(ans>=inf)cout<<-1;
	else cout<<ans;
	return 0;
}

詳細信息

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 6ms
memory: 38040kb

input:

10
1 1 1 1 1 -1 -1 -1 1 -1

output:

-1

result:

ok 1 number(s): "-1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 36112kb

input:

10
1 1 1 1 1 1 -1 1 1 -1

output:

3

result:

ok 1 number(s): "3"

Test #3:

score: 0
Accepted
time: 3ms
memory: 33896kb

input:

1
-1

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 3ms
memory: 36100kb

input:

2000
1 -1 -1 -1 -1 -1 1 -1 1 1 1 -1 -1 -1 1 1 -1 1 1 -1 -1 1 -1 -1 1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 1 1 1 -1 1 1 -1 -1 1 -1 1 1 1 1 -1 -1 -1 1 1 -1 -1 1 1 1 -1 -1 -1 -1 1 -1 -1 1 1 -1 1 -1 1 -1 -1 -1 1 -1 -1 ...

output:

15146

result:

ok 1 number(s): "15146"

Test #5:

score: 0
Accepted
time: 1ms
memory: 33984kb

input:

2000
-1 -1 1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 -1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 1 1 1 1 -1 -1 1 -1 -1 1 -1 -1 -1 1 1 1 1 1 -1 -1 -1 -1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 -1 -1 -1 -1 1 -1 1 1 -1 1 1 1 -1 1 1 -1 -1 -1 ...

output:

24933

result:

ok 1 number(s): "24933"

Test #6:

score: 0
Accepted
time: 6ms
memory: 38060kb

input:

2000
1 1 -1 -1 -1 -1 1 1 -1 1 -1 1 1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 1 1 -1 1 1 -1 1 1 1 -1 -1 1 -1 -1 1 -1 -1 1 -1 1 -1 1 1 1 -1 -1 -1 -1 1 -1 1 -1 1 1 -1 1 1 1 1 -1 1 1 1 1 -1 -1 1 1 1 -1 1 1 1 1 1 -1 -1 -1 1 1 -1 1 1 -1 -1 1 -1 1 -1 -1 1 1 1 -1 -1 1 1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 1 -...

output:

18090

result:

ok 1 number(s): "18090"

Test #7:

score: 0
Accepted
time: 3ms
memory: 34012kb

input:

2000
-1 -1 -1 -1 -1 1 1 -1 -1 -1 1 1 -1 -1 1 -1 1 1 1 1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 1 -1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 1 1 -1 1 1 -1 -1 -1 -1 1 -1 1 1 -1 -1 1 -1 1 1 -1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 1 1 1 -1 1 1 -1 -1 -1 1 -1 -1 1 -1 1 1 1 -1 1 -1 -1 1 1 1...

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

score: 0
Accepted
time: 1ms
memory: 36152kb

input:

2000
-1 1 -1 1 1 -1 -1 1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 1 1 -1 -1 -1 1 -1 1 -1 -1 1 1 -1 1 -1 -1 1 -1 1 -1 1 1 1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 1 -1 1 1 1 -1 1 1 1 1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 ...

output:

9973

result:

ok 1 number(s): "9973"

Test #9:

score: 0
Accepted
time: 1ms
memory: 34064kb

input:

2000
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 ...

output:

499500

result:

ok 1 number(s): "499500"

Test #10:

score: 0
Accepted
time: 1ms
memory: 38244kb

input:

2000
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

499500

result:

ok 1 number(s): "499500"

Test #11:

score: 0
Accepted
time: 3ms
memory: 36116kb

input:

1999
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

499500

result:

ok 1 number(s): "499500"

Test #12:

score: 0
Accepted
time: 1ms
memory: 36192kb

input:

1997
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

498501

result:

ok 1 number(s): "498501"

Test #13:

score: 0
Accepted
time: 1ms
memory: 34012kb

input:

2000
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

-1

result:

ok 1 number(s): "-1"

Subtask #2:

score: 3
Accepted

Dependency #1:

100%
Accepted

Test #14:

score: 3
Accepted
time: 6ms
memory: 36036kb

input:

1
1

output:

0

result:

ok 1 number(s): "0"

Test #15:

score: 0
Accepted
time: 82ms
memory: 52176kb

input:

500000
1 -1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 -1 -1 1 -1 1 1 -1 1 -1 1 1 1 -1 -1 1 -1 1 1 1 1 1 -1 -1 -1 1 -1 1 1 1 1 1 1 1 -1 -1 1 1 -1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 1 1 -1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 -1 -1 -1 1 -1 1 -1 1 1 1 1 -1 1 -1 -1 1 1 -1 1 1 1 1 -1 1 1 -1 -1 1 ...

output:

29737766

result:

ok 1 number(s): "29737766"

Test #16:

score: 0
Accepted
time: 88ms
memory: 54288kb

input:

500000
1 -1 -1 1 1 1 1 1 1 1 1 1 -1 1 -1 -1 1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 1 -1 -1 1 -1 1 1 1 1 -1 1 -1 1 -1 1 1 1 -1 1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 -1 1 -1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 1 1 1 1 -1 1 1 -1 1 -1 1 1 -1 1 -1 -1 -1 -1...

output:

66957355

result:

ok 1 number(s): "66957355"

Test #17:

score: 0
Accepted
time: 87ms
memory: 50732kb

input:

500000
1 -1 1 1 1 -1 1 1 -1 1 1 1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 -1 1 1 1 1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 1 -1 -1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 1 1 -1 -1 1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 1 -1 1 1 -1 -1 1 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 1 -1 1...

output:

50480873

result:

ok 1 number(s): "50480873"

Test #18:

score: 0
Accepted
time: 75ms
memory: 52208kb

input:

500000
-1 1 1 -1 1 1 -1 1 1 -1 1 1 1 -1 -1 1 -1 1 -1 -1 1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 1 1 1 -1 1 1 -1 1 1 -1 1 1 -1 1 1 1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 1 -1 1 1 -1 1 1 1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 -1 1 -1 1 -1 -1 1 1 1 -1 1 -1 1 -1 1 1 1 1 1 -1 1 -1 1 1 1 -1 -1 -1 -1...

output:

-1

result:

ok 1 number(s): "-1"

Test #19:

score: 0
Accepted
time: 85ms
memory: 51104kb

input:

500000
1 1 1 1 -1 -1 -1 1 -1 1 1 -1 -1 1 1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 1 -1 1 1 -1 1 1 -1 -1 -1 -1 -1 -1 1 1 -1 1 1 -1 -1 -1 -1 -1 1 1 1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 -1 1 1 1 -1 -1 -1 1 1 1 -1 1 1 1 1 1 1 -1 1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 1 -1 1 1 1 1 1 1 -1 -1 -1 -1 1 1 -1 1 1 1...

output:

90473670

result:

ok 1 number(s): "90473670"

Test #20:

score: 0
Accepted
time: 55ms
memory: 54376kb

input:

500000
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

31249875000

result:

ok 1 number(s): "31249875000"

Test #21:

score: 0
Accepted
time: 61ms
memory: 51768kb

input:

500000
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -...

output:

31249875000

result:

ok 1 number(s): "31249875000"

Test #22:

score: 0
Accepted
time: 55ms
memory: 52212kb

input:

499999
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -...

output:

31249875000

result:

ok 1 number(s): "31249875000"

Test #23:

score: 0
Accepted
time: 61ms
memory: 51792kb

input:

499997
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

31249375003

result:

ok 1 number(s): "31249375003"

Test #24:

score: 0
Accepted
time: 56ms
memory: 51360kb

input:

500000
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -...

output:

-1

result:

ok 1 number(s): "-1"

Subtask #3:

score: 3
Accepted

Dependency #1:

100%
Accepted

Test #25:

score: 3
Accepted
time: 4ms
memory: 34000kb

input:

10
0 1 0 0 1 1 -1 0 1 -1

output:

9

result:

ok 1 number(s): "9"

Test #26:

score: 0
Accepted
time: 2ms
memory: 33964kb

input:

10
-1 1 0 0 1 0 -1 0 1 -1

output:

10

result:

ok 1 number(s): "10"

Test #27:

score: 0
Accepted
time: 1ms
memory: 34008kb

input:

1
0

output:

0

result:

ok 1 number(s): "0"

Test #28:

score: 0
Accepted
time: 4ms
memory: 36096kb

input:

2000
0 1 -1 -1 1 1 0 1 0 -1 0 0 0 1 0 -1 1 0 -1 1 1 0 0 1 0 -1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 -1 -1 -1 -1 0 0 0 0 0 1 -1 0 0 0 1 -1 0 0 -1 0 -1 0 1 1 -1 0 -1 0 -1 0 0 -1 1 1 -1 0 0 0 0 -1 -1 1 -1 0 0 0 0 0 -1 0 -1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 -1 0 -1 1 1 1 1 0 1 1 0 0 1 0 1 0 -1 -1 0 0 -1 -1...

output:

252956

result:

ok 1 number(s): "252956"

Test #29:

score: 0
Accepted
time: 5ms
memory: 34040kb

input:

2000
1 0 1 -1 -1 1 -1 0 -1 0 -1 1 0 0 -1 1 0 0 -1 0 0 0 -1 -1 0 0 0 0 0 -1 0 0 0 1 0 0 -1 1 1 1 0 1 1 1 0 -1 -1 1 1 1 1 0 -1 1 0 1 0 0 0 0 -1 1 -1 -1 -1 0 0 0 -1 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 -1 0 0 0 -1 0 0 -1 0 -1 0 -1 0 0 1 -1 1 0 0 0 0 0 1 0 0 -1 0 1 0 0 1 1 -1 1 0 0 0 0 -1 0 -1 0 -1 0 0...

output:

262836

result:

ok 1 number(s): "262836"

Test #30:

score: 0
Accepted
time: 3ms
memory: 34060kb

input:

2000
-1 1 1 0 0 0 0 1 0 -1 1 -1 1 0 1 0 1 0 0 1 0 0 -1 -1 0 0 1 0 1 0 -1 0 0 0 0 0 1 0 1 -1 1 0 -1 -1 1 0 -1 0 1 1 -1 0 -1 0 0 -1 1 1 0 -1 -1 0 -1 0 0 0 1 0 -1 -1 -1 0 -1 0 1 1 0 -1 0 -1 1 0 -1 0 -1 1 0 0 1 -1 0 0 0 0 0 0 0 0 -1 0 0 -1 0 -1 1 0 0 0 0 -1 0 1 0 -1 -1 1 -1 0 0 1 -1 -1 -1 1 1 0 -1 0 0 0...

output:

259619

result:

ok 1 number(s): "259619"

Test #31:

score: 0
Accepted
time: 3ms
memory: 33988kb

input:

2000
-1 -1 1 0 0 0 -1 0 0 -1 -1 0 -1 0 -1 0 1 0 0 1 0 0 0 -1 0 0 -1 1 0 1 0 -1 1 -1 -1 -1 -1 0 0 1 0 0 0 -1 0 -1 0 0 1 -1 0 0 0 1 0 0 0 1 0 0 0 1 0 -1 -1 0 1 0 1 -1 -1 -1 1 1 0 1 -1 -1 0 1 0 0 0 0 0 0 -1 -1 0 -1 -1 0 -1 -1 1 1 1 -1 1 0 0 0 1 -1 -1 0 -1 -1 0 0 0 -1 0 1 0 0 0 0 0 -1 0 0 -1 0 -1 0 -1 -...

output:

-1

result:

ok 1 number(s): "-1"

Test #32:

score: 0
Accepted
time: 2ms
memory: 36196kb

input:

1999
-1 1 1 0 -1 -1 0 1 0 0 1 0 -1 1 -1 1 0 1 1 -1 1 -1 -1 0 1 -1 -1 1 0 1 -1 0 -1 -1 -1 -1 1 0 -1 0 -1 1 -1 1 1 0 -1 -1 -1 0 0 1 -1 0 -1 1 1 -1 1 -1 -1 -1 1 1 0 0 0 1 -1 -1 1 1 0 0 1 -1 -1 0 -1 1 -1 1 -1 0 0 -1 0 0 1 -1 0 0 0 1 -1 -1 1 -1 -1 1 0 1 1 1 -1 -1 1 1 0 1 1 1 0 -1 -1 0 -1 0 0 1 1 0 -1 -1 ...

output:

216714

result:

ok 1 number(s): "216714"

Test #33:

score: 0
Accepted
time: 1ms
memory: 34056kb

input:

2000
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 ...

output:

499500

result:

ok 1 number(s): "499500"

Test #34:

score: 0
Accepted
time: 2ms
memory: 36184kb

input:

2000
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

624750

result:

ok 1 number(s): "624750"

Test #35:

score: 0
Accepted
time: 1ms
memory: 38224kb

input:

2000
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 ...

output:

624249

result:

ok 1 number(s): "624249"

Test #36:

score: 0
Accepted
time: 1ms
memory: 33996kb

input:

1998
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 ...

output:

-1

result:

ok 1 number(s): "-1"

Test #37:

score: 0
Accepted
time: 4ms
memory: 36172kb

input:

1999
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 ...

output:

-1

result:

ok 1 number(s): "-1"

Test #38:

score: 0
Accepted
time: 0ms
memory: 36152kb

input:

1999
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

666333

result:

ok 1 number(s): "666333"

Test #39:

score: 0
Accepted
time: 1ms
memory: 34116kb

input:

2000
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

666333

result:

ok 1 number(s): "666333"

Test #40:

score: 0
Accepted
time: 3ms
memory: 36144kb

input:

1999
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

222111

result:

ok 1 number(s): "222111"

Test #41:

score: 0
Accepted
time: 4ms
memory: 34116kb

input:

2000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

0

result:

ok 1 number(s): "0"

Test #42:

score: 0
Accepted
time: 2ms
memory: 36036kb

input:

1910
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

-1

result:

ok 1 number(s): "-1"

Test #43:

score: 0
Accepted
time: 3ms
memory: 36008kb

input:

2000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

572

result:

ok 1 number(s): "572"

Subtask #4:

score: 4
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #44:

score: 4
Accepted
time: 64ms
memory: 46888kb

input:

500000
1 1 -1 0 0 -1 1 -1 0 0 1 1 -1 -1 -1 1 -1 1 0 0 -1 1 1 0 0 0 0 0 1 0 -1 0 -1 1 1 0 0 -1 1 0 0 0 0 0 -1 0 0 -1 1 1 0 0 1 0 0 1 -1 0 1 0 0 0 0 -1 1 0 1 0 -1 0 -1 1 1 0 -1 0 0 0 0 0 0 1 -1 1 -1 1 0 1 -1 0 1 -1 0 -1 -1 1 1 0 1 0 -1 0 0 0 -1 0 -1 0 0 1 -1 1 0 0 1 0 1 0 1 0 0 -1 0 1 1 -1 -1 0 0 -1 -...

output:

15602272809

result:

ok 1 number(s): "15602272809"

Test #45:

score: 0
Accepted
time: 61ms
memory: 47248kb

input:

500000
0 0 1 1 0 -1 1 0 -1 0 0 -1 0 -1 1 -1 0 0 1 0 -1 0 0 0 -1 -1 0 0 0 0 -1 1 0 0 0 -1 0 -1 0 -1 -1 0 0 -1 0 0 1 0 1 0 -1 0 1 1 1 1 0 0 1 0 0 0 -1 1 1 0 -1 1 0 -1 0 1 1 1 1 0 0 0 1 0 1 1 0 -1 -1 0 -1 1 1 -1 1 0 0 1 -1 1 -1 -1 0 0 0 0 1 0 1 1 0 0 0 1 0 -1 1 -1 1 1 0 -1 0 1 -1 -1 0 1 0 0 0 0 -1 0 0 ...

output:

15694076101

result:

ok 1 number(s): "15694076101"

Test #46:

score: 0
Accepted
time: 70ms
memory: 48200kb

input:

500000
1 1 0 -1 1 1 -1 0 0 0 0 1 1 0 0 1 1 -1 0 0 1 1 -1 0 0 -1 -1 -1 0 0 0 0 1 -1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 -1 -1 1 0 -1 0 0 1 0 1 -1 1 -1 1 0 0 -1 0 0 0 -1 -1 0 -1 0 1 -1 0 0 1 -1 0 1 1 1 0 1 0 0 0 0 0 0 -1 1 -1 0 0 0 1 0 1 -1 -1 1 -1 1 0 -1 0 0 0 0 0 0 0 -1 0 1 -1 1 1 0 0 0 -1 0 0 1 0 0...

output:

15625336308

result:

ok 1 number(s): "15625336308"

Test #47:

score: 0
Accepted
time: 66ms
memory: 48212kb

input:

500000
-1 1 0 0 -1 0 0 -1 0 1 0 -1 0 1 0 -1 1 -1 0 1 0 0 0 0 1 0 -1 0 0 -1 0 -1 1 0 -1 1 -1 0 1 -1 1 0 1 0 0 -1 -1 1 -1 1 0 0 -1 0 -1 0 0 0 0 1 0 0 0 0 0 0 -1 0 0 -1 -1 0 0 0 0 -1 -1 0 0 0 -1 0 1 -1 1 0 1 -1 0 0 -1 0 0 -1 0 1 -1 -1 0 0 1 -1 -1 -1 0 0 -1 -1 -1 -1 0 1 1 0 0 -1 1 0 -1 0 -1 0 1 0 0 0 -1...

output:

-1

result:

ok 1 number(s): "-1"

Test #48:

score: 0
Accepted
time: 77ms
memory: 49284kb

input:

499999
-1 0 -1 -1 -1 0 1 -1 1 1 1 0 1 1 -1 -1 -1 1 0 0 1 1 0 0 1 -1 1 0 -1 1 0 1 0 0 1 0 -1 1 1 1 -1 -1 1 -1 0 1 -1 0 1 -1 1 -1 0 0 -1 -1 -1 -1 -1 0 1 1 -1 -1 1 0 -1 -1 1 -1 -1 0 -1 0 0 0 0 -1 -1 0 1 1 0 -1 1 1 1 1 1 0 1 -1 1 -1 0 1 0 0 -1 0 1 1 -1 0 1 -1 0 -1 0 -1 -1 -1 -1 1 -1 1 1 -1 0 -1 -1 0 0 1...

output:

13935079333

result:

ok 1 number(s): "13935079333"

Test #49:

score: 0
Accepted
time: 61ms
memory: 51392kb

input:

500000
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

31249875000

result:

ok 1 number(s): "31249875000"

Test #50:

score: 0
Accepted
time: 51ms
memory: 50212kb

input:

500000
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -...

output:

39062437500

result:

ok 1 number(s): "39062437500"

Test #51:

score: 0
Accepted
time: 37ms
memory: 47644kb

input:

499998
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

39061937499

result:

ok 1 number(s): "39061937499"

Test #52:

score: 0
Accepted
time: 43ms
memory: 47760kb

input:

500000
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

39062312499

result:

ok 1 number(s): "39062312499"

Test #53:

score: 0
Accepted
time: 47ms
memory: 47512kb

input:

499999
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

-1

result:

ok 1 number(s): "-1"

Test #54:

score: 0
Accepted
time: 54ms
memory: 50028kb

input:

499999
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -...

output:

41666583333

result:

ok 1 number(s): "41666583333"

Test #55:

score: 0
Accepted
time: 52ms
memory: 50112kb

input:

499999
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

41666250001

result:

ok 1 number(s): "41666250001"

Test #56:

score: 0
Accepted
time: 48ms
memory: 51712kb

input:

500000
1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -...

output:

13888861111

result:

ok 1 number(s): "13888861111"

Test #57:

score: 0
Accepted
time: 43ms
memory: 43044kb

input:

500000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

0

result:

ok 1 number(s): "0"

Test #58:

score: 0
Accepted
time: 35ms
memory: 43648kb

input:

499100
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

212037

result:

ok 1 number(s): "212037"

Test #59:

score: 0
Accepted
time: 32ms
memory: 43444kb

input:

500000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

252209

result:

ok 1 number(s): "252209"

Subtask #5:

score: 4
Accepted

Test #60:

score: 4
Accepted
time: 3ms
memory: 38052kb

input:

10
3 10 5 -9 7 2 -6 1 8 0

output:

-1

result:

ok 1 number(s): "-1"

Test #61:

score: 0
Accepted
time: 2ms
memory: 38188kb

input:

10
-9 0 -1 7 5 10 6 3 2 -8

output:

13

result:

ok 1 number(s): "13"

Test #62:

score: 0
Accepted
time: 9ms
memory: 34188kb

input:

2000
40667 -598150 -1084780 1201651 1570514 -1859539 -2029075 2941581 -2945945 3038404 3447919 5293872 -5335692 -5669647 5973784 6041345 6346915 -7222112 8820986 -9153143 9563103 9749206 -9894732 -11847193 11987150 12161864 13336572 13528051 -13722732 -13836176 -15497141 -15841563 15862227 16618123 ...

output:

-1

result:

ok 1 number(s): "-1"

Test #63:

score: 0
Accepted
time: 1ms
memory: 34028kb

input:

2000
3038404 -798315545 693574695 172661079 516504064 164016456 193562146 -131746730 382134316 -398886978 188767854 -834289064 -965673210 -826409444 -281381674 450991903 -592752625 81651101 -594873306 -352059270 -651772982 540062674 -769881300 68999588 307151563 -129950325 550154987 354801227 840540...

output:

658039

result:

ok 1 number(s): "658039"

Test #64:

score: 0
Accepted
time: 3ms
memory: 34060kb

input:

2000
-1095 -925 -1049 -1519 951 -1673 -776 345 -38 -1735 -276 -1730 123 -1629 -1896 -1576 -1115 1145 15 797 -948 287 1487 1195 1269 -1240 -1571 -275 -1915 -369 -1221 -1590 -1392 -100 1688 -1287 -241 1130 -1375 -965 669 -147 -307 -795 -1207 1939 120 -305 -915 -1078 -1448 1458 -603 1935 658 774 1471 7...

output:

668545

result:

ok 1 number(s): "668545"

Test #65:

score: 0
Accepted
time: 1ms
memory: 36136kb

input:

2000
1290 1487 -1947 -255 457 -1202 1313 36 -1511 898 1739 987 1809 -1986 -1015 -1127 -703 -223 179 557 199 349 1099 -259 -1401 -1244 -1116 646 -295 1713 1512 127 -1660 343 -1921 -1326 -549 831 1963 -1743 1655 -698 1792 366 1517 -51 404 -1853 -1295 1652 -130 -1562 -1850 -582 1504 1888 822 -24 1807 9...

output:

663841

result:

ok 1 number(s): "663841"

Test #66:

score: 0
Accepted
time: 6ms
memory: 36104kb

input:

2000
56 -1667 -1636 -671 -1311 348 976 1381 -710 -477 -1301 756 -510 495 -1215 -278 1134 950 59 1739 -33 -839 -862 605 761 827 -1708 -1180 -607 1624 -120 -1198 624 -1237 -1874 1788 1005 -331 1266 -467 -1213 1736 -182 594 775 1209 -832 300 1188 -994 -191 -217 1360 -1907 71 436 1294 -590 913 -747 -629...

output:

667052

result:

ok 1 number(s): "667052"

Test #67:

score: 0
Accepted
time: 1ms
memory: 38108kb

input:

1999
-758656 -113741 -374719 7680 -227905 -201318 -200890 -84484 777096 -167712 -126972 -244117 835074 161027 923025 -224756 973701 36622 -913757 -920737 -976062 461264 147694 -162457 358437 -308202 385370 808271 -523703 -303454 -522131 -664739 -505124 306509 948216 948694 -467953 -768055 769796 486...

output:

675957

result:

ok 1 number(s): "675957"

Test #68:

score: 0
Accepted
time: 3ms
memory: 36104kb

input:

1
0

output:

0

result:

ok 1 number(s): "0"

Test #69:

score: 0
Accepted
time: 3ms
memory: 33928kb

input:

2
1000000000 999999999

output:

-1

result:

ok 1 number(s): "-1"

Test #70:

score: 0
Accepted
time: 4ms
memory: 36100kb

input:

2000
999998002 999998004 999998006 999998008 999998010 999998012 999998014 999998016 999998018 999998020 999998022 999998024 999998026 999998028 999998030 999998032 999998034 999998036 999998038 999998040 999998042 999998044 999998046 999998048 999998050 999998052 999998054 999998056 999998058 99999...

output:

999000

result:

ok 1 number(s): "999000"

Test #71:

score: 0
Accepted
time: 7ms
memory: 36204kb

input:

1999
-1000000000 -999012346 -998024692 -997037038 -996049384 -995061730 -994074076 -993086422 -992098768 -991111114 -990123460 -989135806 -988148152 -987160498 -986172844 -985185190 -984197536 -983209882 -982222228 -981234574 -980246920 -979259266 -978271612 -977283958 -976296304 -975308650 -9743209...

output:

0

result:

ok 1 number(s): "0"

Test #72:

score: 0
Accepted
time: 3ms
memory: 34092kb

input:

1999
1998 1997 1996 1995 1994 1993 1992 1991 1990 1989 1988 1987 1986 1985 1984 1983 1982 1981 1980 1979 1978 1977 1976 1975 1974 1973 1972 1971 1970 1969 1968 1967 1966 1965 1964 1963 1962 1961 1960 1959 1958 1957 1956 1955 1954 1953 1952 1951 1950 1949 1948 1947 1946 1945 1944 1943 1942 1941 1940 ...

output:

1998

result:

ok 1 number(s): "1998"

Subtask #6:

score: 0
Wrong Answer

Dependency #5:

100%
Accepted

Test #73:

score: 3
Accepted
time: 108ms
memory: 62604kb

input:

500000
-725 2759 -4173 -4473 4578 -5071 -7897 -7991 9738 -12600 17445 -18596 -20105 -21103 22718 26116 -26973 33169 -33830 34895 37480 -41216 -41665 43933 44687 45286 -46096 46958 47293 -50534 50597 -52520 -57079 57680 58680 -62109 63682 -64495 -64608 64674 -64848 -65420 67176 -74442 -76904 -77098 -...

output:

-1

result:

ok 1 number(s): "-1"

Test #74:

score: -3
Wrong Answer
time: 245ms
memory: 62544kb

input:

500000
716212992 819699933 394255912 695521313 788446410 -466519569 476323400 812543029 724100006 -681244028 -306686799 216473950 496416101 636791486 302599115 190055737 -908659874 -407112922 733684038 -282369420 36611820 323272468 -755065727 -735846631 -22777612 905154351 -694170466 -726666701 7098...

output:

-23151901046471801

result:

wrong answer 1st numbers differ - expected: '41671567967', found: '-23151901046471801'

Subtask #7:

score: 2
Accepted

Dependency #3:

100%
Accepted

Dependency #5:

100%
Accepted

Test #84:

score: 2
Accepted
time: 6ms
memory: 34104kb

input:

2000
-712201807 395965214 845681334 619140248 -741521072 786758881 340213356 -529678837 151707945 327004454 573017024 857965513 -228724921 269122643 961412211 667206872 176451853 628862351 419556721 216401822 -81893212 370970708 -754083788 -883551608 769103150 -603735408 -236144544 -723728591 -19482...

output:

-1

result:

ok 1 number(s): "-1"

Test #85:

score: 0
Accepted
time: 1ms
memory: 34028kb

input:

2000
-207917358 485615334 -706126810 -789660519 629725168 827892248 779265824 560233861 524664590 -393783284 -440021768 315070450 -622473794 489263733 413058741 -593246618 -488814480 840858074 -253700822 353505297 -309466571 -65528378 -1397378 924732667 -528400461 605642479 -516602518 -22775794 8683...

output:

657375

result:

ok 1 number(s): "657375"

Test #86:

score: 0
Accepted
time: 3ms
memory: 34000kb

input:

2000
645 -1877 1717 677 499 387 -1914 -1986 -1705 -1832 275 1799 727 -831 -1132 984 1907 -1193 -514 -1006 -846 1480 -1517 774 563 -187 1178 1044 -1952 -605 1427 -1438 -122 -1371 677 138 -1590 112 -1936 -1033 -703 -281 80 263 -581 -70 209 -837 356 -931 790 666 19 168 -1201 -148 473 1656 -566 -114 -15...

output:

620136

result:

ok 1 number(s): "620136"

Test #87:

score: 0
Accepted
time: 3ms
memory: 38064kb

input:

2000
91 149 -136 -180 -48 15 149 44 45 38 193 -12 -70 61 -174 30 76 -64 -39 -95 115 -150 191 40 19 -179 -8 -171 -7 119 116 -160 172 -167 -26 -111 158 8 -91 -118 -36 -48 -3 -81 -150 190 59 115 -130 133 -97 -129 -125 -154 173 -43 101 -65 90 82 -47 -97 -33 14 98 -116 -138 15 -157 -161 -128 -124 -53 144...

output:

526542

result:

ok 1 number(s): "526542"

Test #88:

score: 0
Accepted
time: 6ms
memory: 34096kb

input:

2000
18 1 -12 4 13 -8 5 -17 0 16 19 -18 16 16 6 -14 13 -2 -10 -8 1 17 18 -5 -14 -15 2 -2 6 20 -7 -4 -15 -9 16 -20 -19 3 -6 1 -8 -1 4 -10 -13 13 -17 5 -17 -11 9 3 19 -7 17 11 3 1 -19 17 20 9 1 -8 5 -2 0 -3 -18 6 -15 -17 16 19 -15 -9 -4 2 -19 20 -1 -6 -13 -9 13 10 10 0 -11 -13 -14 -20 1 -12 18 -13 -1 ...

output:

473295

result:

ok 1 number(s): "473295"

Test #89:

score: 0
Accepted
time: 3ms
memory: 38056kb

input:

2000
0 -2 2 2 -2 2 2 0 1 1 2 1 2 2 -2 0 2 -2 0 0 0 2 0 1 2 0 -2 2 0 0 0 -2 2 2 1 2 2 -2 -2 -2 2 -1 -2 0 1 1 -1 -2 1 2 0 0 -1 1 2 0 -1 0 -2 -2 1 0 1 2 0 2 -1 0 1 0 -1 -2 -2 1 -1 2 -1 -1 0 2 2 -1 1 1 0 -1 0 1 -1 0 0 2 0 -2 2 2 0 -1 0 -1 -2 1 0 0 1 -2 -2 -1 -2 -1 -2 0 2 -1 -1 0 0 2 0 -2 2 0 2 -2 0 1 0 ...

output:

336502

result:

ok 1 number(s): "336502"

Test #90:

score: 0
Accepted
time: 1ms
memory: 38060kb

input:

2000
2 1 0 0 2 1 0 -2 0 -2 0 -1 0 -1 1 2 2 0 0 -2 0 2 1 1 2 0 0 1 1 0 -1 0 0 2 2 1 0 -2 0 -2 2 0 -2 1 0 -1 -2 -2 2 2 -1 -1 2 1 1 -2 1 1 -2 -1 -1 2 0 -2 0 -2 0 0 2 0 -2 -2 -2 -2 0 0 -2 0 2 0 0 0 0 0 0 0 2 -2 0 2 2 0 -1 -1 -1 0 -1 -1 -2 -1 -1 -1 0 1 0 1 0 0 -2 1 0 1 1 -2 -1 0 -2 0 0 0 2 0 2 0 2 2 0 0 ...

output:

330798

result:

ok 1 number(s): "330798"

Test #91:

score: 0
Accepted
time: 3ms
memory: 36152kb

input:

2000
0 1 -2 0 0 -1 1 0 -1 2 0 2 -1 1 0 1 0 1 2 2 -2 0 -2 0 0 0 -1 0 1 -2 -2 0 -1 0 -2 0 2 0 -2 -2 2 0 -2 0 -2 2 2 0 0 0 0 0 2 2 0 -2 1 2 2 0 0 1 2 2 -1 0 -2 1 -1 -2 0 -2 -2 0 -2 -1 0 2 -1 0 1 1 0 1 -1 1 -2 2 2 2 -1 2 -2 2 -1 1 -1 -1 0 1 1 -1 0 0 2 -1 0 0 1 -2 2 2 -1 -2 1 -2 0 -2 0 -2 0 0 0 -2 0 -1 1...

output:

329241

result:

ok 1 number(s): "329241"

Test #92:

score: 0
Accepted
time: 2ms
memory: 38112kb

input:

2000
0 0 0 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 ...

output:

998998

result:

ok 1 number(s): "998998"

Test #93:

score: 0
Accepted
time: 5ms
memory: 36036kb

input:

2000
1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000...

output:

666333

result:

ok 1 number(s): "666333"

Subtask #8:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

0%