QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#703969#114. Construction of HighwayTheZone100 ✓140ms7016kbC++202.3kb2024-11-02 19:00:172024-11-02 19:00:17

Judging History

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

  • [2024-11-02 19:00:17]
  • 评测
  • 测评结果：100
  • 用时：140ms
  • 内存：7016kb
查看
  • [2024-11-02 19:00:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1,c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
#define ll long long
const int N=1e5+4;
int n,b[N];
long long ans;
namespace sz{
	int t[N],c[N];
	inline void clr(int x){
		for(;x<=n;x+=x&-x)t[x]=0;	
	}
	inline void add(int x,int v){
		c[++c[0]]=x;
		for(;x<=n;x+=x&-x)t[x]+=v;	
	}
	inline int ask(int x){
		int ret=0;
		for(;x;x-=x&-x)ret+=t[x];
		return ret;	
	}
	inline void clear(){
		for(int i=1;i<=c[0];i++)clr(c[i]);
		c[0]=0;	
	}
}
namespace lct{
	#define lc ch[p][0]
	#define rc ch[p][1]
	int t[N],siz[N],ch[N][2],fa[N],st[N],top;
	inline bool getson(int p){
		return ch[fa[p]][1]==p;
	}
	inline bool isroot(int p){
		return ch[fa[p]][getson(p)]!=p;	
	}
	inline void pushup(int p){
		siz[p]=siz[lc]+siz[rc]+1;}inline void rotate(int p){int f=fa[p],g=fa[f],r=getson(p);fa[p]=g;if(!isroot(f))ch[g][getson(f)]=p;ch[f][r]=ch[p][r^1];if(ch[f][r])fa[ch[f][r]]=f;ch[p][r^1]=f;fa[f]=p;pushup(f);pushup(p);}inline void pushdown(int p){st[top=1]=p;for(;!isroot(p);p=fa[p])st[++top]=fa[p];for(int i=top;i;i--){p=st[i];t[lc]=t[rc]=t[p];}t[0]=0;}inline void splay(int p){pushdown(p);
		for(;!isroot(p);rotate(p))
			if(!isroot(fa[p]))rotate(getson(p)==getson(fa[p])?fa[p]:p); 
	}
	inline void access(int p){
		for(int pre=0;p;pre=p,p=fa[p]){
			splay(p);
			ans+=(ll)(siz[lc]+1)*sz::ask(t[p]-1);
			sz::add(t[p],siz[lc]+1);
			rc=pre;
			pushup(p);
		}
		sz::clear();
	}
	inline void link(int x,int y){
		ans=0;
		access(x);splay(x);
		fa[x]=y;ch[y][0]=x;
		pushup(y);
		cout<<ans<<"\n";
	}
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)lct::t[i]=b[i]=read();
	sort(b+1,b+n+1);
	b[0]=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)lct::t[i]=lower_bound(b+1,b+b[0]+1,lct::t[i])-b;
	for(int i=1,x,y;i<n;i++){
		x=read();y=read();
		lct::link(x,y);
	}
	return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 1ms
memory: 5604kb

input:

2
804289384 846930887
1 2

output:

0

result:

ok single line: '0'

Test #2:

score: 7
Accepted
time: 1ms
memory: 5668kb

input:

10
505335291 738766720 190686789 260874576 747983062 906156499 502820865 142559278 261608746 380759628
1 3
1 5
5 7
3 8
1 4
3 10
7 6
5 9
5 2

output:

0
0
0
1
0
1
0
0
0

result:

ok 9 lines

Test #3:

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

input:

100
205554747 483147986 844158169 953350441 612121426 310914941 210224073 856883377 922860802 495649265 8614859 989089925 378651394 344681740 29100603 816952842 21468265 552076976 87517202 953369896 374612516 787097143 126313439 207815259 287632274 886964648 220723886 119448938 444268469 865680799 6...

output:

0
0
0
0
0
0
0
0
0
1
0
0
2
0
0
0
0
0
2
0
3
4
3
0
0
1
2
1
0
2
0
2
0
5
6
1
1
2
0
0
1
1
0
1
0
2
4
0
4
1
2
2
3
0
2
0
0
0
8
0
2
2
0
1
3
2
8
2
0
0
2
0
0
1
0
4
2
0
3
0
2
6
3
0
1
1
0
0
4
6
1
1
0
0
1
6
1
2
0

result:

ok 99 lines

Test #4:

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

input:

300
968078302 287724084 410622275 558519327 460165364 773440538 901520026 404622364 417397029 665131386 88500545 246243955 225558715 439197965 991031404 638538415 465622903 21944942 554535402 204144150 501551718 340552605 608463969 970964280 749109574 736758719 557300323 501093883 605082721 41831082...

output:

0
0
0
0
0
0
0
4
0
0
2
0
0
0
0
0
0
1
0
0
0
5
0
0
1
0
0
1
5
4
2
7
5
0
0
1
0
0
3
2
2
2
5
0
0
0
0
0
3
6
5
3
0
4
3
4
2
4
0
6
0
0
0
0
6
3
0
3
4
4
7
1
6
3
0
7
3
0
2
8
3
0
0
0
2
4
0
11
2
6
4
7
9
4
0
8
3
3
12
2
6
6
4
4
0
5
3
5
3
8
4
0
0
3
0
7
0
0
0
12
0
0
8
0
0
0
4
5
16
4
0
2
12
0
11
4
0
3
5
4
3
6
19
4
3
2
0...

result:

ok 299 lines

Test #5:

score: 7
Accepted
time: 1ms
memory: 5668kb

input:

500
590011676 99788766 131925611 171864073 317159277 171035633 602511921 963050650 69979074 919854382 33661027 589806849 86105861 475191199 894416411 550050021 780437021 583787227 893281829 550277487 650366415 990569006 968873680 612872374 163967332 764676461 72834384 841258874 802348053 82417968 25...

output:

0
0
0
0
0
0
0
0
0
0
2
12
0
10
0
2
0
4
2
2
0
0
10
12
0
0
10
3
8
0
0
0
0
0
11
0
0
0
0
0
0
4
8
3
15
7
2
0
0
2
16
0
0
0
5
4
18
14
6
2
0
8
12
21
10
0
1
4
27
0
0
0
6
0
6
6
0
2
0
0
0
20
0
0
2
0
1
6
6
11
4
0
0
0
8
9
2
8
0
0
5
0
13
2
0
2
7
9
6
2
5
3
15
0
0
6
6
16
0
12
0
20
0
8
9
6
21
0
6
0
6
9
6
30
7
2
6
3
2...

result:

ok 499 lines

Test #6:

score: 7
Accepted
time: 1ms
memory: 3608kb

input:

500
290852542 66988986 717401113 865455666 182811309 730087286 385463287 531287044 665477003 111229779 137441936 26865324 886053606 671359094 894851843 478150617 183526401 99262093 326652024 913157945 831189952 666778271 422466541 365798623 685286190 667869012 484134621 222111029 100237558 722796576...

output:

0
0
0
0
0
0
0
0
0
0
0
2
0
0
8
0
5
0
0
2
4
0
4
6
2
2
0
4
6
0
5
6
0
6
6
0
4
0
10
5
4
2
10
0
0
3
2
3
0
0
0
6
0
5
6
9
0
0
0
1
1
2
11
6
10
0
0
0
0
9
1
2
0
14
0
15
0
2
0
3
2
0
0
5
23
2
11
4
12
3
0
4
0
10
6
0
5
0
0
0
2
10
0
0
15
4
0
11
0
2
0
6
0
5
0
3
4
2
10
8
0
5
4
20
5
5
6
3
5
2
0
14
1
5
19
15
2
16
3
0
1...

result:

ok 499 lines

Test #7:

score: 7
Accepted
time: 1ms
memory: 5680kb

input:

500
45618678 863967300 272579900 461085872 21961326 105564444 138782587 68574098 291851601 118852154 131251316 191929322 641615332 751255527 909053866 351969721 462792179 691535747 693715571 143120737 928880505 114632964 732145789 94870505 34412750 561287885 781032962 630849393 77144258 155493231 38...

output:

0
0
0
0
0
0
0
0
0
0
0
3
4
0
0
0
0
2
0
2
0
5
1
0
0
0
3
0
0
5
6
4
0
3
0
7
1
1
6
0
0
0
0
1
2
0
0
11
0
3
3
19
0
12
2
8
7
0
6
3
3
4
0
0
8
0
5
4
5
5
0
4
0
3
1
2
4
0
10
12
4
1
0
2
15
0
8
3
4
0
1
4
1
14
16
0
0
1
3
0
6
6
4
9
1
4
0
2
0
2
1
11
0
5
8
4
11
1
0
0
9
5
7
0
1
15
18
8
4
4
4
4
1
6
1
4
4
6
6
5
5
1
0
11...

result:

ok 499 lines

Test #8:

score: 7
Accepted
time: 1ms
memory: 5740kb

input:

500
757547897 695630745 945246243 94247550 49268312 533158094 863977183 801112022 980174778 403165314 181261048 577956982 464612197 823671048 936502656 381480695 967846101 239125399 12803266 613336598 147866706 904405039 225761898 966870463 603465941 585950248 319905335 142628938 358260056 7260884 8...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #9:

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

input:

500
444454916 502197875 436864166 770686808 899516531 994794654 552099821 351221479 547895243 568662053 116124857 982508164 159126659 994372690 898982038 197124816 193049010 710365141 472749247 939754300 203469646 449577281 561696332 586204726 129139400 509788395 661656565 439714064 591742750 493076...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #10:

score: 7
Accepted
time: 1ms
memory: 5692kb

input:

500
215069296 311962009 86128679 385788726 753820419 394002378 255532676 906573272 54404748 679162308 131589624 179656374 97642529 100364174 876662345 113981582 577648321 198294839 891854072 208116669 424885269 107628345 65686956 299460182 479838563 460457229 25739513 864854524 712507289 151291767 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #11:

score: 7
Accepted
time: 1ms
memory: 5600kb

input:

500
292699226 248582804 819144113 10387544 66932928 974608011 8748636 198676205 836143905 389604207 583879741 563569934 435633414 574835010 638828242 697688141 286490445 46871902 318827995 224999039 96700275 940389332 495461465 397431505 531499861 434401289 935726823 805878076 101166413 266584703 72...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #12:

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

input:

500
574043894 981675017 210563957 769562664 120453154 99483608 606202021 252907318 277317363 165448856 61204332 381680683 862447906 634786445 722590525 317435151 17971530 268346170 793038026 415590563 670392196 661394501 63853654 211023426 450833187 91060204 606850909 716844870 674386143 21775201 74...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #13:

score: 7
Accepted
time: 1ms
memory: 5700kb

input:

500
65126306 423020469 220551191 69652764 36215333 307669182 884896190 292871525 71108050 451363275 863133126 844652817 305997796 140648185 596943388 490624029 583960228 384908059 843957336 854342707 107784031 91280499 27295886 781653927 223888692 216119105 523514491 995249228 368185371 374826185 53...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #14:

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

input:

500
293886900 342407238 302519958 552815566 196011631 98949956 310911217 58366891 62428184 228478280 339899803 256954480 738191188 173394777 278132514 211754964 796034386 783566459 489116750 758777593 49307512 35463173 949823865 415661458 796786679 747389228 917150586 842852837 175077659 655565974 8...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #15:

score: 7
Accepted
time: 1ms
memory: 5768kb

input:

500
1 335 485 167 63 88 17 421 45 138 4 142 413 49 215 424 162 107 386 477 353 259 295 447 109 9 299 359 270 497 382 244 143 396 399 194 26 140 268 134 343 293 471 258 422 475 57 478 289 148 29 329 96 400 58 217 237 241 290 355 350 32 403 35 139 220 223 271 253 218 113 10 6 454 192 305 416 472 195 3...

output:

0
0
1
1
1
1
3
3
3
3
3
3
3
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
...

result:

ok 499 lines

Test #16:

score: 7
Accepted
time: 1ms
memory: 3648kb

input:

500
472896955 990749241 447062221 129110975 525541408 931666208 214864874 142169787 531446368 718782898 913618852 123773464 825488293 824687514 893662732 764382487 382781239 23638743 183923689 685397660 554504181 85442892 324582231 391254131 122366862 898909853 269500776 550546117 861226181 48622358...

output:

0
0
1
0
0
1
2
3
2
2
2
2
1
0
2
3
1
2
5
2
2
5
2
4
5
2
1
1
2
5
5
4
6
3
6
2
3
5
4
3
6
6
7
6
4
3
6
3
7
2
1
2
8
4
8
7
9
3
5
3
4
0
5
5
6
5
5
6
8
5
8
4
12
10
12
11
10
8
11
10
7
10
6
6
8
4
5
7
10
6
7
8
8
11
10
13
12
13
7
8
8
9
11
3
5
6
5
6
4
4
5
9
6
11
12
12
7
6
8
6
9
8
10
7
9
10
13
13
10
15
13
15
7
14
17
7
...

result:

ok 499 lines

Test #17:

score: 7
Accepted
time: 1ms
memory: 5764kb

input:

500
886608726 504308535 109686045 178577959 733543847 345748973 719389824 752532822 258094387 542664384 558965849 119882419 302735585 288721626 353919018 365543372 634508348 708687332 4671699 80798848 741517802 835203055 514712214 659425939 460293324 627950885 61773373 581894193 510634011 33834871 5...

output:

0
0
0
0
1
1
2
3
1
2
1
2
0
1
2
6
5
2
1
3
6
3
3
3
2
4
3
5
5
1
3
4
7
6
4
7
7
5
6
5
8
8
2
3
5
6
6
3
7
5
4
3
5
4
1
3
4
9
3
3
4
7
5
3
8
7
4
7
9
5
7
3
6
11
6
6
6
11
8
11
11
12
9
5
8
9
11
5
6
5
7
4
10
8
9
6
5
11
8
5
11
6
7
6
8
10
10
8
9
3
3
6
3
7
10
12
9
7
7
8
9
11
7
6
8
6
9
3
6
11
10
8
17
8
10
11
14
16
13
...

result:

ok 499 lines

Test #18:

score: 7
Accepted
time: 1ms
memory: 5700kb

input:

500
654005961 118037236 386308216 156833090 961894895 44123290 322408197 489097382 579910683 431820770 451994462 112558931 861006552 652978156 162766587 967430901 840344339 334942128 295732952 71211314 150680965 204791609 554835180 505439123 745888608 374543721 813068317 265125732 186709223 89950918...

output:

0
0
0
0
1
0
2
1
1
2
1
1
1
1
2
2
2
1
1
5
3
5
4
4
4
5
5
0
1
4
7
7
4
5
7
6
1
2
2
4
6
5
6
8
3
5
8
4
2
6
4
6
3
5
7
4
1
6
6
7
3
3
5
12
10
9
5
8
8
5
6
7
10
6
11
10
9
7
4
7
1
8
10
10
6
4
8
10
8
5
9
5
5
7
8
6
10
9
8
9
11
6
4
3
10
9
11
7
5
11
12
9
9
11
6
7
11
5
8
7
4
9
7
8
2
5
6
3
9
12
14
10
12
12
7
10
13
9
1...

result:

ok 499 lines

Test #19:

score: 7
Accepted
time: 1ms
memory: 5680kb

input:

500
881785153 731096568 89881583 322485749 749880766 265395973 884065837 451371009 281245281 890041248 827544451 734439158 76769765 6745499 682790296 26430238 733503799 289783778 537563988 36208859 944554670 21579938 290679382 908816022 844170156 172450880 467659292 879583769 837907469 785014697 991...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #20:

score: 7
Accepted
time: 1ms
memory: 5700kb

input:

500
143917523 218403783 24315423 627077081 229337806 737768267 513683845 309530204 118991374 498020336 199190064 169699238 206894717 782326156 517630170 857629923 696067475 239016424 508227116 285934479 328389627 81290977 831910820 920155905 735586683 829193746 797956253 10138417 144134826 484521558...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #21:

score: 7
Accepted
time: 1ms
memory: 5708kb

input:

500
806370886 659318482 29755186 102946938 701020863 491644997 816197493 744834398 397764874 631370648 140019690 77296260 707446387 698413474 24931125 498404060 187424739 350298383 569284062 401164380 376400101 824760867 316255991 280636886 213950714 147594035 336142440 990028819 445165253 575622959...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #22:

score: 7
Accepted
time: 1ms
memory: 5756kb

input:

500
1 1 1 2 1 2 2 1 2 2 2 2 1 2 2 2 1 2 2 1 2 2 1 1 2 2 2 2 2 2 2 2 2 2 1 2 1 2 2 1 2 2 2 2 1 1 2 1 2 1 1 2 2 2 2 1 1 1 1 2 2 2 1 1 2 1 1 2 2 2 2 1 1 1 1 1 2 2 2 1 2 2 2 1 1 1 2 1 1 2 2 2 1 2 1 2 2 1 2 2 2 1 2 1 2 2 1 1 1 2 1 2 2 1 1 2 1 2 1 2 1 2 1 1 2 1 1 1 1 2 2 1 2 2 1 1 1 1 1 2 1 2 1 2 2 1 1 2 ...

output:

0
0
0
0
0
2
0
2
0
3
0
0
0
0
0
3
0
0
0
0
0
0
0
0
2
0
0
0
3
0
0
6
0
1
2
0
8
0
0
0
3
8
4
0
0
0
4
0
4
0
0
4
0
8
0
0
2
0
0
0
0
6
0
6
0
0
0
0
5
0
9
8
0
0
0
5
2
0
2
9
12
0
2
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
6
4
0
0
6
2
0
7
0
3
12
0
0
0
6
0
0
0
0
4
0
6
0
0
1
0
0
0
2
3
0
0
2
2
8
4
2
0
0
2
0
0
0
0
4
6
4
2
3
4
...

result:

ok 499 lines

Test #23:

score: 7
Accepted
time: 1ms
memory: 5680kb

input:

500
3 5 5 5 5 3 5 10 6 10 7 8 5 4 10 2 8 2 7 4 4 2 5 9 3 3 4 4 5 10 6 7 6 2 4 10 7 8 9 2 9 7 9 6 10 1 7 8 4 3 3 7 7 7 8 1 1 1 7 5 2 4 2 8 5 7 9 1 4 10 5 3 6 5 8 8 5 4 7 9 9 9 7 7 6 6 9 6 9 5 1 10 10 4 9 5 10 8 7 5 7 1 9 4 6 6 1 2 2 7 2 2 6 9 10 3 4 8 10 4 5 2 4 4 7 2 10 8 1 7 3 9 9 1 3 6 9 5 10 2 2 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
3
2
2
1
0
2
0
0
0
0
4
4
4
3
2
1
0
2
2
2
1
0
0
4
0
0
4
3
0
1
0
0
0
0
0
0
4
0
0
0
0
3
6
0
1
4
0
0
4
0
8
0
0
2
4
2
5
8
2
0
12
3
0
7
6
0
7
6
4
0
0
2
0
4
6
0
2
7
4
0
1
6
0
8
0
0
0
0
0
2
0
3
4
7
21
0
2
14
3
0
5
4
2
4
1
0
9
4
3
3
0
3
1
0
0
5
2
6
0
2
0
5
0
3
24
0
3
0
4
0
0
...

result:

ok 499 lines

Test #24:

score: 7
Accepted
time: 1ms
memory: 3612kb

input:

500
24 10 17 30 24 2 23 14 34 6 7 41 1 47 3 3 4 49 46 9 9 35 1 14 25 19 19 18 40 28 29 14 39 45 45 14 48 19 27 33 24 33 23 25 32 28 29 37 26 25 46 34 11 46 50 35 17 18 3 8 47 33 23 35 29 17 50 26 35 27 8 11 9 33 35 42 10 13 29 37 39 24 20 50 21 19 34 37 38 38 47 36 20 19 22 48 36 22 25 22 48 33 32 8...

output:

0
0
0
2
0
0
0
0
0
0
5
0
0
3
0
0
1
0
0
0
0
3
0
0
5
0
10
3
2
0
8
0
6
0
0
0
4
0
1
2
0
6
6
0
3
0
6
3
3
7
0
0
2
0
4
0
4
9
7
0
0
0
0
4
0
0
7
4
17
4
0
1
1
3
8
3
6
11
12
0
1
7
7
2
6
4
1
5
0
3
5
0
5
10
15
6
0
4
0
3
0
0
3
0
0
0
0
3
9
4
6
0
7
0
18
7
1
15
3
0
2
5
8
4
6
0
0
9
11
2
0
22
9
6
3
0
9
0
1
0
3
3
2
6
12...

result:

ok 499 lines

Test #25:

score: 7
Accepted
time: 1ms
memory: 5684kb

input:

500
162 289 161 69 261 94 216 253 287 213 176 95 246 158 65 183 24 183 277 270 65 256 179 99 223 113 204 158 126 54 182 39 94 42 160 54 188 127 58 174 92 233 268 89 142 85 23 217 267 300 239 83 7 169 181 281 33 137 138 159 190 72 249 283 113 160 36 300 287 145 226 78 129 245 218 270 29 240 239 48 29...

output:

0
0
0
0
0
0
0
2
7
0
8
0
0
2
3
0
0
0
1
1
1
2
0
0
5
3
0
2
1
0
1
6
3
8
6
0
4
4
0
2
0
3
8
0
0
0
0
3
0
0
3
2
0
5
4
1
2
0
2
3
1
6
6
0
0
0
4
3
12
4
0
6
10
5
4
0
4
5
4
12
5
0
6
6
0
1
4
6
3
0
1
3
0
2
6
11
2
8
3
0
1
0
3
12
5
2
8
4
9
6
0
4
2
6
0
2
3
6
6
4
16
0
2
19
14
3
18
0
0
11
0
4
0
3
7
5
11
4
14
0
10
3
4
5...

result:

ok 499 lines

Test #26:

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

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #27:

score: 7
Accepted
time: 1ms
memory: 5708kb

input:

500
1 355 107 451 223 488 51 70 398 77 352 466 332 72 178 234 372 27 186 233 499 319 96 138 327 126 421 464 146 221 195 453 302 42 491 482 457 65 85 286 184 199 91 9 389 183 379 442 308 244 43 414 224 351 52 164 301 429 83 148 425 265 242 137 472 387 384 50 230 194 160 117 366 400 173 139 196 436 40...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #28:

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

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #29:

score: 7
Accepted
time: 1ms
memory: 5628kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #30:

score: 7
Accepted
time: 1ms
memory: 5700kb

input:

500
1 387 39 437 194 369 111 375 344 177 49 86 87 403 453 60 183 407 293 69 144 480 93 302 102 4 245 125 316 331 263 82 205 171 187 145 481 12 115 127 469 285 142 391 451 256 209 424 204 217 56 349 195 465 98 343 154 218 5 500 104 303 74 156 148 353 345 140 352 85 400 472 271 314 496 174 396 10 428 ...

output:

0
0
1
1
1
1
3
3
3
3
3
3
3
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
...

result:

ok 499 lines

Test #31:

score: 7
Accepted
time: 1ms
memory: 5696kb

input:

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

output:

0
0
1
0
1
0
1
2
1
2
0
0
1
3
2
2
5
5
5
5
2
2
2
3
4
3
3
3
3
4
5
4
3
1
6
8
8
3
5
8
4
5
6
5
4
1
6
9
3
6
2
3
7
3
3
5
1
9
4
6
8
4
9
7
3
7
3
5
6
5
8
7
4
9
6
6
9
2
3
8
3
8
6
2
6
7
11
5
6
7
7
4
3
11
11
7
5
11
8
10
7
6
8
3
7
7
11
8
11
10
10
10
10
8
6
8
2
8
12
10
5
9
9
5
6
3
11
13
13
13
7
11
11
11
12
13
5
9
8
...

result:

ok 499 lines

Test #32:

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

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #33:

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

input:

500
668248 350453 601690 460727 603425 216243 318066 135374 720648 343597 400269 943776 173203 636567 40382 489638 539435 540802 878199 108827 327909 600448 490788 888125 564150 593915 708437 282763 851016 515512 214174 35615 382316 815864 496341 985740 548458 330759 637465 269105 674355 554086 7292...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #34:

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

input:

500
995459 539038 936089 878707 439542 758247 639002 619480 908076 696086 12734 743079 435852 969848 494508 15150 722352 957496 627368 119111 673131 929327 932328 763534 733950 782478 297538 782057 291706 354173 888288 287164 409562 824376 682222 849103 582622 321223 984935 7050 533660 997668 266480...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #35:

score: 7
Accepted
time: 1ms
memory: 5696kb

input:

500
679152 710470 353216 456541 1153 783238 115408 762520 100213 367914 707555 92809 816934 923499 972393 535673 531170 959487 179256 676673 643945 651182 17878 10592 267065 177121 101244 412936 549116 9571 969528 228267 236392 322743 201160 237544 622332 316567 516415 238896 200832 223969 331705 53...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #36:

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

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #37:

score: 7
Accepted
time: 1ms
memory: 5744kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #38:

score: 7
Accepted
time: 1ms
memory: 5680kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #39:

score: 7
Accepted
time: 1ms
memory: 5680kb

input:

500
499344 701121 404159 443144 284217 202050 875595 601070 205468 960913 70779 78402 255889 635417 811166 169640 758453 913381 805037 17556 159905 63832 377141 163360 21925 882644 707532 301756 1782 753630 629029 501125 971102 33187 460621 255318 751588 336215 372740 957056 813479 443518 551809 585...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #40:

score: 7
Accepted
time: 1ms
memory: 5604kb

input:

500
564409 894627 442401 846655 178444 182285 993501 614142 413465 522343 929104 401396 115495 177872 514342 468442 58785 922286 418059 597701 842307 516329 857634 839178 100393 830325 133658 639114 257809 809795 43551 822217 704421 2304 668871 399216 700940 178723 13357 114404 701065 942460 32152 3...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #41:

score: 7
Accepted
time: 1ms
memory: 5600kb

input:

500
767009 329211 508949 720282 967819 935741 174148 439533 881472 191980 984296 472957 56165 25717 450725 624220 199055 10182 885247 36021 940408 876609 775488 490819 498233 670865 484598 866125 529688 462436 73149 296696 307998 98450 533329 275816 34190 707476 231700 915661 415807 215995 904970 98...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #42:

score: 7
Accepted
time: 1ms
memory: 3660kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #43:

score: 7
Accepted
time: 1ms
memory: 5672kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Test #44:

score: 7
Accepted
time: 1ms
memory: 5756kb

input:

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

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499 lines

Subtask #2:

score: 9
Accepted

Dependency #1:

100%
Accepted

Test #45:

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

input:

1000
677741241 611911302 516687480 39653885 807009857 115325624 224653906 83069271 106860982 922406372 876420181 322411829 259609598 356425748 318253491 883344302 229978181 871801539 567764311 334753944 440409295 768869742 447440213 147132416 825732307 813670414 897413452 991129618 396963908 6587545...

output:

0
0
0
0
0
0
0
1
0
0
2
0
0
0
0
0
0
0
2
0
0
5
0
2
0
2
0
2
0
0
0
4
2
6
3
0
0
1
8
0
4
2
0
0
2
6
3
2
5
2
3
4
0
4
1
0
3
1
2
2
4
0
5
4
0
0
0
0
7
9
0
9
7
6
2
5
3
5
3
0
10
0
0
2
6
6
0
4
10
3
0
0
0
2
5
10
0
0
12
0
2
0
6
0
3
11
2
5
6
5
0
1
3
6
10
0
8
0
0
2
5
0
6
8
14
0
4
3
9
0
9
2
10
4
5
0
0
1
3
3
3
0
3
6
2
3
...

result:

ok 999 lines

Test #46:

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

input:

4000
331330604 197953681 10832165 138423563 597828154 365076975 372218871 14115695 211964560 854812120 836062091 804031484 545004832 665440083 664335747 811141375 580260746 716952096 275794845 740334921 877233386 630362529 68514649 318329905 774954594 688264692 778327479 68526655 970144488 414592324...

output:

0
0
0
0
0
0
0
2
0
0
3
0
0
6
3
0
2
2
2
0
0
3
6
0
2
0
9
5
1
0
0
0
0
0
2
3
6
3
0
0
4
1
9
0
6
0
0
4
6
0
9
0
7
0
0
8
0
15
3
4
0
4
0
0
0
0
0
6
0
5
6
7
2
0
3
1
0
0
1
3
0
11
12
1
3
7
2
0
0
6
5
0
0
0
4
0
10
1
12
0
6
0
21
9
5
0
1
4
16
3
2
5
1
2
0
0
7
4
0
7
4
6
0
5
0
0
2
10
0
7
0
4
3
8
0
5
0
2
6
9
1
8
4
10
3
5...

result:

ok 3999 lines

Test #47:

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

input:

4000
64858754 868075536 587306287 96943540 474515220 477962989 602021526 106822049 256422292 797259273 664740152 80530855 842344225 141135887 30161163 753234428 26543869 586223704 927294471 24193669 343422809 512685174 645625633 598888500 749502809 523516823 776027999 250576243 435579438 148511994 6...

output:

0
0
0
0
0
2
0
0
0
6
0
8
0
0
7
4
0
0
0
0
0
0
0
3
0
4
0
0
2
0
5
9
0
0
0
6
0
6
0
7
6
3
8
8
2
8
0
15
0
0
0
0
0
9
0
2
5
0
0
5
0
2
4
0
13
5
0
11
0
11
5
0
0
0
5
10
6
0
4
0
7
12
1
2
4
0
0
0
2
0
6
5
0
1
4
3
8
0
9
0
7
0
0
2
2
4
4
6
5
0
6
4
0
6
0
5
14
4
0
6
2
6
11
9
4
9
0
6
5
11
13
13
3
4
7
11
9
14
19
0
8
11
0...

result:

ok 3999 lines

Test #48:

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

input:

4000
784236096 446136712 76643923 112826243 255498021 721903023 886588039 99549628 354436126 791422770 609665825 553434311 40321630 432281783 217978420 739182879 281494014 344236701 617554714 403811144 837295490 427647579 161882354 896734669 749295963 361086028 778412041 375150328 964842200 94563333...

output:

0
0
0
0
1
0
1
1
0
1
0
0
0
2
0
2
2
0
0
0
0
1
0
0
2
0
1
0
0
2
0
2
0
0
0
1
1
4
2
2
0
0
3
1
0
2
0
2
0
3
2
2
2
1
1
0
2
0
2
1
2
0
6
0
0
0
3
1
0
0
0
5
1
3
5
1
0
3
4
2
0
0
0
0
6
0
3
1
8
0
2
3
8
0
4
4
5
2
3
2
1
5
1
2
4
4
1
4
3
6
0
2
3
1
0
0
2
4
3
0
7
6
0
11
0
5
2
5
1
5
8
0
0
1
6
8
0
3
0
0
0
0
4
3
2
3
1
4
3
1...

result:

ok 3999 lines

Test #49:

score: 9
Accepted
time: 1ms
memory: 3708kb

input:

4000
433930399 106412058 640477418 59117271 120519272 893586919 27842904 104660315 528734570 642221071 421852382 956612033 316030464 814558261 559292257 581442363 630503357 184650219 237629168 806952868 269524442 272182306 852616827 137335156 678481049 229356480 729092988 576577470 528713576 6979455...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #50:

score: 9
Accepted
time: 2ms
memory: 5764kb

input:

4000
22703043 775430625 146127781 94947693 848505077 9508247 188480486 48617756 650016565 664181093 396803472 236150689 620538730 141761644 928002420 532320783 2440521 56519763 899760863 164624465 811615512 167220260 430825876 345707393 594321764 140923852 727570434 702464378 72500293 579175811 3023...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #51:

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

input:

4000
817947204 285792582 713518102 113235753 710201797 185222886 475816658 123082300 681293614 514110652 277102820 717881695 896145020 516987041 200601993 449262729 269058419 49464264 595883975 557356479 248638205 15796853 35515593 590482546 603437460 142393983 681333378 838934205 546343046 33287917...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #52:

score: 9
Accepted
time: 1ms
memory: 3788kb

input:

4000
1 2969 452 2404 2590 3236 2195 45 2476 3752 1115 2012 952 3991 3324 3234 2178 3290 1183 3373 3415 2945 3385 3864 957 2043 3983 898 2018 3918 222 194 708 3216 603 496 1303 3726 1493 2277 2142 2201 518 3330 3055 2144 1341 635 757 95 2141 481 3443 3688 482 3287 1157 2770 1825 636 3872 1787 2554 24...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #53:

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

input:

4000
445886965 63394092 750746374 524625526 672559177 423741655 294401041 628362155 396957660 145205099 437777672 310700226 109331672 822702759 249099570 118229805 289837463 249691289 842017746 239503988 367406802 572196423 452863254 353901825 584177033 819591822 858013578 87013272 335287735 5085300...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #54:

score: 9
Accepted
time: 1ms
memory: 3760kb

input:

4000
170114158 350727315 53326981 729706651 384292857 371710984 655461568 500999774 883817040 590578524 757721889 413827971 982730641 380647878 326915378 647794618 163027442 37396383 153284757 138526806 881278159 144866276 202929924 10339565 922232384 98440653 666045103 160528504 860662386 643791999...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #55:

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

input:

4000
442404120 57271374 730616173 587581238 443703432 142588572 794243872 873436477 410423697 775745637 22012176 83626434 865921888 851080364 83704310 96917731 209783530 690838196 857761259 949397924 868854699 967080415 6743547 1133226 24775529 41414184 220369858 350874758 494133274 131939465 380453...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #56:

score: 9
Accepted
time: 2ms
memory: 5704kb

input:

4000
250540310 777452323 241693986 264293545 23708036 363188877 937112173 947391647 995131692 104821010 689337484 482459692 365688119 881253591 161105086 664597180 796621021 127558323 867317167 346559596 42791824 389894975 826806004 673460371 604837677 169590872 71950261 792088346 660283372 15190351...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #57:

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

input:

4000
1 4000 402 439 3023 1492 1816 1486 172 2538 144 2188 3566 3398 604 3423 1790 2845 861 3837 2879 3748 1860 2323 3370 681 2874 711 3314 1194 530 2021 1189 1285 2810 2228 3761 283 2114 2473 3703 3446 3238 3324 3903 1915 1934 3159 2818 1852 1671 3994 828 2775 2345 797 2294 592 1601 948 2839 1719 34...

output:

0
0
1
1
1
1
3
3
3
3
3
3
3
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
...

result:

ok 3999 lines

Test #58:

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

input:

4000
891558057 759625131 620196132 863680794 462296714 103749001 115643288 962712763 566632766 18428651 318492217 588433278 238719 385892319 538750064 175221428 610749958 871203884 857322929 229113962 205217308 603817167 639428881 109108288 749675601 169029793 171187663 37461817 482864847 987804524 ...

output:

0
0
1
0
0
1
2
2
0
2
1
3
1
3
3
4
0
5
2
2
1
4
2
5
3
6
1
3
2
6
4
7
9
8
3
6
1
9
4
4
0
6
7
5
6
9
5
6
4
4
2
5
6
3
6
6
5
8
3
2
2
4
9
6
6
10
11
6
6
6
11
10
3
11
7
11
9
10
11
13
7
11
12
10
11
9
9
5
5
8
7
9
10
9
6
9
2
2
11
6
8
6
13
10
6
7
4
6
1
4
6
7
8
5
11
5
7
2
10
12
7
10
9
5
8
7
6
14
13
5
15
11
6
7
9
11
8
...

result:

ok 3999 lines

Test #59:

score: 9
Accepted
time: 2ms
memory: 5636kb

input:

4000
895503949 542295515 732467272 538448018 376502031 304039781 810227662 498131589 618245971 261676 632701236 45131817 683440306 832065911 231469526 281457736 964177788 693283596 49831274 935068320 66089077 190496626 116707270 789173388 392106817 784376685 288169697 643444318 338160672 593740064 7...

output:

0
0
0
1
1
1
2
2
2
3
1
3
0
0
2
2
3
4
2
3
4
2
3
5
1
4
3
5
3
5
6
9
2
5
3
5
5
3
2
9
2
5
3
5
4
6
6
9
4
6
4
4
6
5
6
7
2
3
6
5
3
5
3
11
6
8
7
8
10
6
12
12
11
8
4
10
5
5
10
8
4
9
8
5
12
4
10
11
12
8
6
10
9
7
6
10
5
8
4
8
9
5
10
7
4
11
5
8
11
9
9
11
6
10
9
5
10
5
13
10
11
7
6
4
7
13
10
12
12
14
4
6
11
6
8
6
...

result:

ok 3999 lines

Test #60:

score: 9
Accepted
time: 4ms
memory: 5636kb

input:

4000
38172162 462009156 739866429 646384955 108170642 74553572 598820728 554066788 618510579 736395060 704831844 732879830 124030803 490876333 394576137 302984730 979136535 792518493 509692543 683140961 297268415 990499519 99807657 964119028 681003982 318577147 475940982 641873824 126050020 26324077...

output:

0
0
0
1
1
1
1
0
2
3
2
1
1
0
5
1
3
1
3
4
5
3
3
1
5
4
3
2
4
2
4
1
6
5
4
3
4
4
8
3
1
1
4
6
4
7
9
8
9
7
8
6
7
8
8
5
4
8
7
5
2
4
8
3
6
1
7
10
7
4
6
7
7
8
3
11
6
5
7
9
10
10
10
5
3
5
8
9
6
7
7
10
6
7
9
8
11
7
6
8
9
8
9
10
11
8
6
8
10
5
3
4
9
6
13
10
4
9
6
6
6
3
3
8
7
6
14
9
10
11
13
14
11
16
10
9
19
13
3
...

result:

ok 3999 lines

Test #61:

score: 9
Accepted
time: 2ms
memory: 5704kb

input:

4000
452148190 765498549 885741814 138739663 704432560 67253298 100123431 223386831 107846692 593900895 852541105 262538385 420386474 236750088 959514148 633528058 888234330 726810538 854767473 398835711 680545319 305214745 414389795 449208200 616521605 797035104 875877441 932267487 217039410 602842...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #62:

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

input:

4000
200743878 821342672 348947501 981338659 306863945 740757664 785950167 573784270 58954439 729325150 344583271 740508123 20025398 247742307 30508454 575582532 356611020 86866056 716731699 24606931 951585500 939570533 72361544 500761395 826018325 515693746 6256541 55186009 557294373 32326103 88755...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #63:

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

input:

4000
89489438 38467674 223139970 746429319 500084791 529405413 393123547 240179984 63575815 547859601 186766352 603355424 35033893 147820582 25482066 226589995 398790051 239894107 537229463 717020432 303102877 842315686 726121817 346932660 696230290 58969721 666782253 840714632 19173229 980563306 80...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #64:

score: 9
Accepted
time: 2ms
memory: 5720kb

input:

4000
2 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 2 2 1 1 2 2 2 1 2 1 1 2 1 1 2 1 1 1 2 1 1 2 1 2 1 1 2 2 1 1 2 1 2 1 1 2 2 1 2 1 1 2 1 1 2 2 1 2 2 2 1 1 1 1 2 2 1 1 1 2 1 2 2 1 2 2 2 2 2 1 2 2 2 2 2 2 2 1 1 1 2 1 1 1 2 2 2 2 1 2 1 1 1 2 1 1 2 2 2 1 2 1 1 2 1 2 1 2 2 1 2 2 2 1 2 1 2 1 2 2 2 1 1 2 2 1 2 1 1 1...

output:

0
0
0
0
0
2
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
4
0
0
0
2
8
1
4
0
1
2
0
0
0
8
0
8
0
0
0
4
0
0
0
3
0
3
0
12
2
0
10
0
0
1
2
0
2
4
0
0
8
0
0
4
0
4
0
5
0
0
0
0
5
2
0
0
0
0
2
6
6
6
0
0
0
0
2
7
1
0
4
6
0
0
6
5
16
0
0
0
12
0
0
0
1
0
0
0
1
0
10
2
0
0
1
10
2
3
0
0
5
3
2
0
0
0
24
1
0
3
0
0
4
5
6
0
0
0
0
0
2
8
14
0
...

result:

ok 3999 lines

Test #65:

score: 9
Accepted
time: 2ms
memory: 5784kb

input:

4000
6 5 6 5 3 3 8 7 6 4 2 6 5 6 6 3 2 6 3 9 1 3 1 5 10 10 3 2 4 7 10 1 1 7 5 5 1 5 1 6 8 5 3 3 10 1 7 1 6 1 2 8 3 2 2 2 3 6 5 9 2 6 9 5 4 6 9 4 10 2 1 9 8 4 3 7 4 2 10 1 2 1 9 5 4 2 8 7 8 5 7 1 2 7 5 6 2 6 9 3 9 2 4 6 5 6 4 8 7 3 8 1 5 8 7 9 10 6 7 9 10 5 9 2 1 6 9 5 1 9 7 1 10 2 6 4 10 9 3 8 4 3 8...

output:

0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
2
0
1
0
2
0
6
0
3
0
6
4
0
0
5
5
6
0
0
0
0
0
4
4
1
0
0
4
2
0
5
9
3
2
0
0
2
4
0
0
1
3
0
0
4
7
10
10
1
6
14
4
0
4
4
7
6
6
0
4
15
6
2
9
0
0
3
5
0
0
0
3
2
4
7
0
0
0
0
6
0
0
7
3
0
8
1
12
0
12
0
0
1
3
4
0
2
0
3
0
5
6
0
8
0
4
5
0
14
0
3
2
0
0
4
4
0
0
0
4
0
6
8
3
0
3
9
8
20
0
...

result:

ok 3999 lines

Test #66:

score: 9
Accepted
time: 3ms
memory: 5716kb

input:

4000
341 339 469 324 31 243 27 122 237 432 363 288 402 432 189 141 327 122 259 380 53 168 8 277 183 1 283 86 7 74 125 199 264 93 22 146 188 400 267 424 332 481 64 85 413 252 225 91 225 336 470 277 3 330 405 185 182 187 122 40 112 98 238 375 190 259 20 229 158 286 153 341 119 68 426 383 171 2 473 395...

output:

0
0
0
0
2
0
2
0
0
0
0
0
0
5
11
0
0
0
0
6
0
0
0
0
0
6
0
3
6
0
2
6
20
9
0
3
0
0
5
0
15
11
0
0
3
0
5
8
0
0
4
0
9
0
0
0
12
0
21
3
0
2
9
3
4
2
1
2
0
6
0
0
0
0
12
5
10
15
0
7
8
6
0
0
7
15
18
0
0
0
9
4
3
0
6
0
8
10
0
1
3
13
12
10
2
55
0
3
0
26
23
0
19
8
12
8
0
0
1
8
0
0
2
7
12
8
17
10
8
0
0
0
3
16
3
10
15
...

result:

ok 3999 lines

Test #67:

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

input:

4000
1553 1985 863 85 557 1673 18 810 1614 1545 1669 889 1063 91 114 1256 1304 34 495 1760 653 448 464 179 1085 651 614 488 102 1557 485 6 1893 1347 90 802 1371 460 1611 985 356 1280 225 1770 1370 338 1025 1026 723 1871 785 1728 670 1248 1906 107 1898 519 946 351 427 1782 709 320 1129 1150 1121 851 ...

output:

0
0
0
0
0
0
0
0
1
0
0
2
2
0
0
0
0
0
2
8
0
0
3
1
0
0
3
0
0
2
1
1
1
0
16
2
4
0
1
4
4
3
0
1
2
0
2
4
0
9
0
12
0
2
4
0
0
0
2
2
0
2
2
5
1
8
3
0
2
0
0
2
0
2
6
2
5
2
7
1
2
0
1
2
1
1
3
2
1
0
0
0
6
7
4
0
0
0
5
4
4
4
0
12
0
1
0
2
0
6
0
17
6
1
0
5
0
8
2
3
4
4
1
3
7
2
2
0
13
4
2
8
0
10
8
0
0
5
0
3
2
9
0
6
1
2
1
...

result:

ok 3999 lines

Test #68:

score: 9
Accepted
time: 1ms
memory: 3752kb

input:

4000
36 21 3 16 1 32 19 4 2 28 16 27 26 3 21 40 6 26 26 27 20 40 7 28 18 40 17 22 7 4 4 2 24 38 10 24 21 20 27 15 7 34 1 32 36 13 24 34 30 9 20 10 1 18 37 18 9 6 31 8 1 26 9 24 15 10 39 36 30 18 10 28 11 2 12 39 6 35 32 35 35 11 36 27 20 25 36 28 22 26 35 22 11 36 5 26 5 35 13 26 12 14 6 23 7 17 21 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #69:

score: 9
Accepted
time: 1ms
memory: 3756kb

input:

4000
1 1058 152 2931 3966 99 2858 910 1115 2446 2112 2430 3239 81 3917 2561 1567 3603 2801 3888 1956 3375 478 1968 2853 3056 2262 2425 3232 3701 2941 1247 2981 461 1799 3432 3897 933 68 613 1958 879 2345 1726 1259 782 798 3387 804 2851 2894 3576 2990 37 2161 1091 1811 1354 1963 2925 917 1378 3396 14...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #70:

score: 9
Accepted
time: 1ms
memory: 5716kb

input:

4000
2 15 6 7 40 13 2 15 30 17 17 25 33 40 1 19 9 33 21 2 22 27 25 17 33 21 30 19 8 1 33 9 8 38 7 39 3 8 6 24 16 14 1 9 13 1 19 13 33 40 15 6 18 31 23 10 3 4 29 10 37 13 18 4 10 24 34 4 23 39 28 30 12 28 30 17 20 9 29 5 40 35 10 17 25 24 26 27 28 6 28 24 18 5 19 20 20 12 23 2 3 2 24 14 21 13 22 1 21...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #71:

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

input:

4000
37 24 9 30 5 34 1 15 4 26 38 11 21 6 17 17 28 30 31 13 1 13 22 29 6 32 13 40 27 29 39 16 5 39 37 9 32 30 23 28 15 13 38 35 10 6 12 37 35 34 1 36 38 23 16 35 14 28 34 33 8 33 40 12 31 36 20 23 25 35 10 40 7 39 26 8 4 29 4 38 15 4 33 12 18 40 7 32 27 32 16 35 24 15 6 7 2 18 29 19 12 30 10 10 20 3...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #72:

score: 9
Accepted
time: 3ms
memory: 5784kb

input:

4000
1 2518 265 1796 2982 358 1815 382 1377 2084 1093 3072 2970 1381 162 2018 3431 692 3831 198 1878 577 3047 1627 3537 3594 3755 30 2457 1679 582 3184 1015 2797 2199 211 284 3006 2487 3806 410 904 2029 1653 49 3576 879 2230 2963 3051 3579 2097 1843 2800 2903 648 1451 1573 2307 1939 3819 655 3966 13...

output:

0
0
1
1
1
1
3
3
3
3
3
3
3
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
...

result:

ok 3999 lines

Test #73:

score: 9
Accepted
time: 3ms
memory: 5704kb

input:

4000
4 25 5 29 24 10 14 23 37 21 14 6 38 11 15 12 30 30 15 12 23 18 3 33 5 39 34 24 29 17 8 33 33 13 13 16 22 26 30 10 39 3 7 28 5 13 39 26 3 13 37 25 22 31 9 27 21 3 10 10 11 9 2 35 21 6 10 35 24 39 36 14 34 35 1 30 7 39 16 1 4 12 18 17 35 26 3 15 20 4 24 30 13 17 16 25 15 25 11 38 16 39 11 1 25 3 ...

output:

0
0
0
1
0
0
1
1
2
2
2
1
0
1
1
4
1
3
3
4
3
5
3
2
2
4
1
3
3
5
5
4
4
9
4
4
3
7
8
1
4
7
3
6
1
5
6
6
5
6
2
4
3
7
7
7
9
5
5
7
3
8
11
4
7
9
9
6
2
3
4
6
4
5
5
12
6
9
12
6
6
9
3
2
6
10
8
8
10
6
10
11
3
4
9
8
8
5
9
9
4
7
7
9
4
5
8
9
10
2
7
10
13
8
7
9
8
8
4
4
8
4
6
7
10
8
14
14
14
12
12
9
10
6
12
16
11
11
4
9...

result:

ok 3999 lines

Test #74:

score: 9
Accepted
time: 2ms
memory: 5800kb

input:

4000
26 19 21 27 7 4 27 14 9 40 14 36 28 1 14 1 25 23 35 32 38 19 14 20 25 26 2 24 20 8 10 38 26 22 16 24 17 2 37 25 2 3 12 21 3 25 13 19 39 39 3 37 18 16 8 34 33 2 17 5 9 19 2 26 40 9 9 17 11 37 33 4 39 5 16 33 21 28 4 20 27 6 8 36 21 15 29 5 8 38 9 16 16 2 33 7 11 1 23 13 30 8 16 20 4 23 13 24 2 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #75:

score: 9
Accepted
time: 2ms
memory: 5748kb

input:

4000
631745 332576 870439 881772 989052 511219 206741 78742 698136 803522 68220 70370 165036 497438 618267 190627 527023 484417 716347 634370 422089 311454 468971 905919 649066 108289 523974 248936 568637 534429 81099 200381 383356 467889 598504 372407 495459 321596 967500 193595 125118 552072 26396...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #76:

score: 9
Accepted
time: 2ms
memory: 5756kb

input:

4000
562824 612472 76925 630356 309430 754263 480871 375412 938296 485874 251863 124272 106330 951280 186751 215669 641227 90571 82968 998437 398510 395349 809483 175401 249708 623154 93688 174075 553361 981198 849009 116184 110021 442285 262891 419450 196547 743762 311214 134843 229635 563076 25911...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #77:

score: 9
Accepted
time: 1ms
memory: 3744kb

input:

4000
816388 317963 762743 219427 355278 763985 556206 491897 613943 777774 389368 385406 584132 721010 436908 130411 452796 265811 531574 79878 302645 791398 891105 656500 250178 714176 229360 311528 339358 170494 317652 672097 4808 596746 891523 360086 877082 447729 368334 491024 741854 757701 3927...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #78:

score: 9
Accepted
time: 1ms
memory: 5712kb

input:

4000
24 39 2 40 10 34 31 13 31 32 29 10 16 14 14 36 31 26 10 36 9 24 33 19 24 28 28 25 17 22 39 33 12 40 32 13 34 14 25 24 6 13 33 21 19 38 8 9 16 9 36 24 32 21 34 7 8 21 23 16 2 22 8 5 21 31 17 6 37 2 29 2 6 14 14 16 3 22 16 18 30 12 33 14 32 26 12 31 7 35 38 40 16 38 5 28 20 13 34 16 6 14 17 12 19...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #79:

score: 9
Accepted
time: 1ms
memory: 5672kb

input:

4000
16 39 40 33 34 25 19 22 23 13 38 18 33 1 28 2 29 26 26 5 6 23 8 23 13 38 22 22 17 21 22 24 11 21 17 4 37 35 17 20 39 15 37 31 7 16 32 36 33 10 32 38 32 40 20 37 29 34 18 5 6 39 28 17 11 4 20 8 30 37 19 21 3 7 11 9 22 35 36 14 36 28 4 19 19 23 15 7 8 24 11 14 22 38 30 25 34 1 32 15 37 10 27 39 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #80:

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

input:

4000
4 24 27 4 31 39 6 32 8 12 26 32 1 36 37 17 21 38 4 19 34 23 2 34 6 22 37 14 35 35 25 30 18 3 34 1 1 31 32 9 34 9 32 34 4 20 11 17 17 6 27 10 28 20 4 33 1 32 7 27 27 23 17 36 17 2 28 9 24 12 17 17 20 40 10 16 19 12 24 36 18 10 37 5 29 32 30 30 24 28 8 2 2 24 29 18 17 17 26 40 20 35 16 39 26 18 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #81:

score: 9
Accepted
time: 2ms
memory: 5608kb

input:

4000
391224 327309 496179 87830 352944 492980 127507 323640 950288 264274 677636 934207 159735 762803 539422 12085 116628 664443 319946 392040 599777 814889 14348 41539 695321 286064 220699 782313 188857 666056 494922 96432 993364 991100 184262 862659 432 311768 186299 950719 576041 380286 401277 73...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #82:

score: 9
Accepted
time: 2ms
memory: 5728kb

input:

4000
14231 428823 39137 452251 56426 500963 625755 15075 504857 827858 205661 185704 869771 989661 74109 326027 796876 160470 903741 873224 85124 979080 919256 954589 192467 121192 213991 217856 800682 865137 930970 814912 293959 970107 267162 866736 987421 892917 881810 492277 237126 87470 677980 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #83:

score: 9
Accepted
time: 2ms
memory: 5676kb

input:

4000
117929 248754 639322 260513 317473 795703 132569 758227 382741 14496 918336 26286 312705 376642 868509 464924 84401 580430 380256 645707 241672 484692 576783 486077 638474 695074 699971 189767 601960 410889 965143 719888 175994 120816 496752 9818 432871 145672 284396 815611 160167 202731 358248...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #84:

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

input:

4000
4 30 29 37 29 17 10 32 19 31 16 17 33 26 11 23 36 29 37 38 5 19 35 26 5 26 32 32 7 27 12 10 8 40 38 36 8 7 20 19 30 35 35 22 21 37 36 16 25 32 5 29 10 31 6 14 17 29 37 23 7 40 24 14 32 21 2 31 20 13 9 1 7 35 14 19 31 9 26 15 40 30 35 1 21 1 14 37 21 3 19 28 2 34 33 25 14 26 16 25 38 24 25 5 11 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #85:

score: 9
Accepted
time: 2ms
memory: 5692kb

input:

4000
32 6 36 34 8 30 10 23 15 39 10 18 2 19 26 39 28 33 1 14 28 36 20 19 23 3 22 7 33 36 36 24 1 23 10 40 12 19 22 18 9 23 36 11 1 13 1 20 5 1 34 33 36 5 11 19 7 24 17 39 19 12 15 11 26 16 2 37 34 23 7 34 37 2 36 37 14 37 17 10 37 2 2 25 6 4 3 5 28 19 35 38 22 1 9 7 16 2 35 1 25 33 35 13 34 22 10 39...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Test #86:

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

input:

4000
7 20 24 37 39 6 6 32 18 13 19 28 37 13 32 7 33 5 32 18 6 34 35 13 22 38 31 17 36 4 6 2 23 21 30 21 26 27 5 35 40 15 15 28 27 6 34 20 2 25 29 39 10 23 12 31 12 34 7 7 37 4 40 11 16 30 24 33 16 28 28 7 2 2 34 29 39 19 40 1 4 28 39 5 2 2 36 13 36 34 11 32 30 10 35 5 31 18 30 39 5 17 5 6 10 31 26 8...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3999 lines

Subtask #3:

score: 84
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #87:

score: 84
Accepted
time: 7ms
memory: 3996kb

input:

10000
595422260 506549999 979315721 197619616 638339383 470018494 387913058 533053797 924132909 451061723 343000805 96448509 278581779 584129417 471142528 63049747 489200897 812165064 669658225 562145723 900323814 739512683 525968013 79472855 976108843 903512344 159660306 757791195 877471767 6429795...

output:

0
0
0
0
1
0
0
1
0
0
0
0
0
2
2
1
1
0
0
0
0
0
0
5
0
0
3
0
1
0
11
4
1
0
3
0
0
5
2
0
0
0
6
1
0
2
3
5
0
0
8
2
12
9
0
1
6
0
6
5
2
6
3
0
4
0
2
0
2
2
8
0
0
1
3
0
2
3
9
3
0
3
3
16
5
0
6
0
0
0
7
8
6
7
4
5
0
2
15
0
12
0
1
6
0
3
8
0
4
6
4
7
1
4
2
4
2
11
6
8
15
3
0
2
2
0
16
0
0
18
0
0
5
14
2
6
11
10
0
14
0
8
5
3...

result:

ok 9999 lines

Test #88:

score: 84
Accepted
time: 17ms
memory: 5992kb

input:

30000
164365246 62436715 12788021 378038487 187980202 4521332 843456414 62437131 851288592 56742937 769560522 358005630 653859761 267941988 977274566 94192634 23625535 753713764 256193745 266321763 807114913 643992684 221560022 415870092 927986278 935921898 463553048 529518532 849601379 545356508 56...

output:

0
0
0
1
1
0
3
0
1
1
0
1
1
0
3
0
0
3
1
3
6
0
2
0
0
3
1
6
2
0
0
1
2
0
0
3
1
0
0
0
1
0
5
0
2
2
3
1
0
1
0
3
4
5
0
3
1
2
3
12
0
0
3
0
3
2
3
0
1
0
1
4
2
0
1
1
1
0
1
17
6
2
2
1
1
5
2
0
0
1
0
2
0
5
0
6
4
4
0
11
5
0
2
2
2
4
2
0
2
1
0
0
4
2
3
2
3
0
0
1
2
8
6
3
2
11
2
0
2
5
2
5
0
2
0
1
11
4
3
4
3
0
0
3
5
7
3
4...

result:

ok 29999 lines

Test #89:

score: 84
Accepted
time: 89ms
memory: 6760kb

input:

100000
872855759 541703725 894906729 475247015 807434126 534888390 214051441 439030385 847754143 428037359 189032001 541039029 87537335 868648661 404444460 107579257 693296261 615723894 43546623 880929192 633584401 451430521 823145335 597121394 913439 942631188 684536554 418920100 789434285 28899405...

output:

0
0
0
0
2
0
0
2
0
0
0
3
1
2
3
1
0
3
2
1
0
0
0
3
5
0
0
0
0
1
1
1
0
3
1
0
1
0
0
4
4
2
3
2
1
2
3
2
5
0
0
0
2
7
0
3
0
0
5
0
2
16
0
4
0
4
4
0
6
3
3
6
4
0
3
2
0
0
2
0
10
2
0
5
2
7
10
0
4
4
25
5
0
0
0
0
0
3
12
1
9
3
4
10
4
0
13
0
7
16
1
1
0
1
7
10
5
0
10
0
0
3
0
18
2
8
20
0
14
1
1
0
0
8
2
6
3
4
0
0
6
8
0
0...

result:

ok 99999 lines

Test #90:

score: 84
Accepted
time: 81ms
memory: 6740kb

input:

100000
433193334 87051810 843206931 719096999 270913414 55662659 657214985 27525456 684703596 18827865 598361275 635396028 371136663 532166834 886999541 117092324 203809265 381635217 677721185 483171715 580544368 250654576 411726958 819794624 914738821 935734530 940875275 218449364 641316857 6113855...

output:

0
0
0
0
0
1
2
0
0
3
0
0
0
0
0
0
2
0
4
1
4
0
0
2
1
0
1
0
0
2
3
0
2
3
6
0
2
7
0
0
1
0
2
0
0
0
8
0
2
4
2
0
1
8
2
3
0
4
2
1
0
0
1
0
0
1
0
8
3
4
1
0
5
6
6
10
4
0
2
5
0
0
0
7
3
3
4
8
1
0
13
7
10
0
2
2
3
6
11
0
6
4
1
4
2
4
8
4
0
0
0
8
0
4
17
4
6
9
2
0
3
3
19
12
4
3
0
8
14
2
6
1
1
1
6
4
0
0
0
3
10
1
2
3
0
4...

result:

ok 99999 lines

Test #91:

score: 84
Accepted
time: 89ms
memory: 6740kb

input:

100000
71552492 568002588 800151944 820522181 966386353 513422766 106436525 480893868 608636689 469477650 948076232 893496395 663731412 64302275 315675364 137721816 732627523 319170823 251983540 106192614 482956083 67164133 97622179 3856641 923972126 29335121 165542947 118910650 597365103 30909908 1...

output:

0
0
0
0
0
0
0
0
0
4
0
0
9
1
5
0
0
0
0
0
5
4
0
0
1
0
0
0
0
0
0
0
3
0
12
0
2
0
12
1
1
0
4
0
0
1
6
2
0
0
2
1
4
6
2
0
0
14
2
10
0
5
0
7
2
0
5
0
3
1
0
2
0
27
2
3
1
0
3
0
5
28
0
9
0
0
0
2
3
2
6
9
8
5
4
0
10
0
0
7
2
16
0
3
15
0
2
3
6
9
12
0
1
7
0
26
0
4
11
24
0
0
34
0
2
2
4
0
1
31
4
2
0
8
8
6
0
20
0
2
4
20...

result:

ok 99999 lines

Test #92:

score: 84
Accepted
time: 33ms
memory: 6820kb

input:

100000
637319535 121160865 831669624 997247529 512641110 45614501 557701146 932349526 606777282 922735691 369482576 4253382 107065650 815539070 817787148 14852133 259340987 108329973 52259664 874739843 309985539 889329312 708135695 332835105 13514632 974348461 460263879 953125553 553121038 848182651...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #93:

score: 84
Accepted
time: 34ms
memory: 6532kb

input:

100000
135438876 604915106 793028839 107371166 138098561 434465074 17289977 464398013 462264575 459395931 725707660 120694883 340339178 429941520 179168360 52322654 872981150 126811800 646069417 438304898 220550995 728395858 412300464 526270812 974893363 17381048 843384571 809401609 538328237 609807...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #94:

score: 84
Accepted
time: 35ms
memory: 6440kb

input:

100000
769152458 157351935 746483638 350677018 609465273 962055394 312311823 987821887 455551433 902043106 70706142 373860531 770935997 103537504 749755186 61779145 467873827 910533084 280975374 51605062 189456784 603367113 85929936 849440725 40124893 95584135 58269382 541863038 548893733 494279719 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #95:

score: 84
Accepted
time: 27ms
memory: 6696kb

input:

100000
1 79920 81047 48930 93789 30645 1357 46029 69849 22761 45531 25526 99694 24336 75363 76931 62246 20532 5237 95950 21561 76088 23014 82976 69837 52486 2115 97882 46812 11430 2270 33046 65544 5235 7010 11675 75551 11247 49169 33984 65313 37253 38345 90008 53761 85148 16407 2365 82418 63226 1928...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #96:

score: 84
Accepted
time: 40ms
memory: 6804kb

input:

100000
144213656 721894651 721667632 663483757 514488465 896659875 911726334 149234149 492247984 676946884 945355987 877562779 416018100 560946927 417393871 65249735 114987279 943186465 463880919 38765242 739638730 918062096 825936021 523625001 158352856 138159487 134496141 145916175 161080571 79809...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #97:

score: 84
Accepted
time: 35ms
memory: 6884kb

input:

100000
861698271 686468192 105061564 849966226 106037375 332670737 658154543 261747173 375361637 56359721 145251740 845188758 304423566 92379195 87409384 589444229 241708389 107542282 601300631 710713282 35381607 212923442 116201467 219596466 136895419 901581880 296042472 936370641 561664461 3043148...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #98:

score: 84
Accepted
time: 37ms
memory: 6696kb

input:

100000
99761982 819106064 650472229 430839674 411834287 818879477 461276904 940830294 142880965 754558291 527603165 952582367 672580097 87947256 214942397 188148551 717494767 21770659 143572518 932152800 90499605 62216140 522817519 66162830 8824672 929881263 839815862 825509432 174559962 519398785 9...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #99:

score: 84
Accepted
time: 36ms
memory: 6904kb

input:

100000
97421965 465303126 165186358 662547892 965800466 175305347 428379539 734322144 410254783 34545046 998897764 988706849 681334923 885001539 979130275 649230448 605373711 227545626 967595831 182240648 907399313 156297771 321785896 926161179 683028042 269481762 785503887 748304740 525104980 44476...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #100:

score: 84
Accepted
time: 118ms
memory: 6760kb

input:

100000
1 28915 14456 4172 43626 21804 67892 54986 47314 27369 85083 41386 71417 35759 3943 29230 11494 77133 95416 33221 82388 26694 19625 3714 73133 14435 91736 22103 49420 69731 64576 40859 80254 41075 7649 50532 65699 75794 37660 70550 21481 63015 48027 55574 25685 79384 30928 55585 96645 50050 3...

output:

0
0
1
1
1
1
3
3
3
3
3
3
3
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
...

result:

ok 99999 lines

Test #101:

score: 84
Accepted
time: 140ms
memory: 6528kb

input:

100000
949097239 424576068 588127418 417964883 630389961 230035955 803602582 125300334 773737233 32821780 942676598 885818790 608557167 592687819 680362066 543733247 658098100 800199138 906017165 72160689 586988752 493775629 245218962 929277603 427076547 579845984 33337866 787728342 928119898 349072...

output:

0
0
0
1
0
0
0
2
2
3
1
1
1
1
4
5
4
2
5
2
4
0
1
2
5
5
3
3
3
4
9
7
5
4
6
4
7
6
3
3
4
7
5
4
4
5
6
5
5
9
9
1
5
6
8
2
5
6
7
6
4
5
7
8
5
8
8
9
8
9
9
3
5
4
3
6
4
4
3
7
4
10
5
11
6
4
9
4
9
7
2
10
7
7
5
12
7
10
10
9
9
10
6
10
7
9
8
8
6
8
10
10
5
8
8
10
8
6
8
9
11
9
5
11
10
8
8
14
10
14
8
10
10
13
11
8
13
12
9...

result:

ok 99999 lines

Test #102:

score: 84
Accepted
time: 140ms
memory: 6756kb

input:

100000
225920385 921396012 771930732 628795119 101153701 401848522 83207339 605049077 670204491 159983394 131180438 187747801 646018405 108255463 21858648 937874198 167666347 419953249 896197877 609451817 788110353 342693728 144851422 33606543 21373785 224512955 861622136 997252880 490091922 3929102...

output:

0
0
0
0
0
0
1
3
3
3
1
1
1
2
5
1
2
3
3
1
2
4
4
3
4
6
4
5
2
2
3
3
4
6
6
7
4
5
3
5
4
2
4
10
8
7
7
6
1
6
4
4
4
4
7
8
6
5
3
3
7
2
8
9
3
6
6
12
5
8
14
8
10
7
5
9
11
10
12
8
6
12
8
7
10
6
6
3
8
11
13
6
5
9
11
7
5
10
8
10
7
7
8
8
7
4
6
4
5
3
8
6
3
4
7
2
7
7
10
9
8
9
12
12
8
11
15
16
9
4
4
7
7
11
5
11
16
10
...

result:

ok 99999 lines

Test #103:

score: 84
Accepted
time: 139ms
memory: 6524kb

input:

100000
304017515 361664461 595026011 735686740 56195208 371364647 349169093 468269775 228815178 711416796 94353566 636191312 408733694 431213088 42641490 368885130 823795294 814241770 527777191 855599912 566391678 927337523 849195768 271344650 167306153 834558016 943645340 824955997 544966787 169764...

output:

0
0
1
0
0
0
1
3
2
2
1
3
0
2
0
4
1
4
3
4
3
4
2
6
2
3
2
0
3
1
1
7
3
1
3
6
6
4
2
2
4
6
7
10
4
2
3
7
6
7
2
7
6
8
7
3
3
6
5
8
7
6
7
12
7
8
5
9
10
7
11
9
7
8
3
8
8
9
7
6
6
12
5
8
7
6
8
11
6
7
5
4
7
5
7
10
6
10
6
8
11
6
7
6
8
8
6
7
5
6
10
5
10
7
6
8
9
11
11
10
6
9
8
7
6
7
9
8
4
10
5
10
7
9
13
11
12
12
10
1...

result:

ok 99999 lines

Test #104:

score: 84
Accepted
time: 61ms
memory: 6552kb

input:

100000
497123319 510262902 366142964 371508032 944729913 368947984 425496815 632351232 35077943 754200761 183415083 954546842 461395257 592625380 880700897 883297155 245582394 57343321 502053253 907751641 122411677 326829492 657820784 20988956 165580137 539652400 231797082 674316153 758912350 921821...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #105:

score: 84
Accepted
time: 61ms
memory: 6968kb

input:

100000
831846447 544064883 618739334 475234940 609193049 578123206 579211132 85138405 445858749 336773557 352964279 74847846 444711016 845828256 520318886 709709513 485626097 61014637 5882098 961188844 750263807 287985101 808739065 881326982 63627336 785411677 800998565 500407254 823177636 345033574...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #106:

score: 84
Accepted
time: 61ms
memory: 6440kb

input:

100000
415008261 553396959 243500100 881374467 256724490 86718038 991304919 991570141 884801636 750073027 517838199 724442311 808378784 145322007 483251519 41291987 472906624 990106550 767724216 7055646 891452828 167812402 503351317 686828541 973985464 610137903 93939519 20449349 300555007 11053690 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #107:

score: 84
Accepted
time: 70ms
memory: 6736kb

input:

100000
2 1 1 2 1 1 1 1 2 2 1 2 2 2 1 1 1 2 2 1 2 2 2 1 1 2 2 1 2 2 1 1 2 1 2 2 1 2 2 2 2 1 1 1 2 2 1 2 1 1 1 2 2 2 2 1 1 1 1 2 2 1 1 1 2 2 1 2 2 2 2 1 2 2 1 2 1 1 1 1 1 1 2 1 1 2 1 1 2 1 1 2 2 1 2 1 2 2 2 1 2 1 1 1 1 1 2 1 2 1 2 2 1 1 2 1 2 2 2 2 1 2 1 2 2 2 2 1 2 1 2 1 2 2 1 2 1 1 2 2 1 1 1 1 2 1 2...

output:

0
0
0
0
0
0
0
2
0
2
0
0
0
0
0
0
2
0
2
1
0
4
0
1
0
1
2
0
0
0
0
1
0
0
0
0
0
2
0
1
0
6
0
0
0
0
0
4
1
0
0
1
0
0
0
0
0
0
0
1
0
2
0
2
4
0
4
0
0
0
0
0
0
4
4
0
1
2
12
0
0
0
6
0
2
0
2
0
0
2
0
4
0
0
6
0
4
4
5
2
0
5
0
2
0
3
0
4
1
0
0
0
8
0
1
0
3
0
0
6
0
8
0
0
3
2
0
2
2
3
2
1
0
6
5
0
0
2
4
0
0
0
0
0
4
6
0
2
3
0...

result:

ok 99999 lines

Test #108:

score: 84
Accepted
time: 77ms
memory: 5928kb

input:

100000
62 57 92 74 84 66 99 91 95 40 99 2 55 14 14 11 72 23 19 100 99 56 57 58 92 96 21 59 35 49 76 96 57 67 21 40 85 19 82 31 11 80 32 17 45 98 27 16 72 97 68 71 52 24 80 43 19 52 2 5 52 29 52 8 95 72 99 31 43 80 62 5 11 45 21 55 42 99 22 66 95 41 36 47 17 67 41 87 18 94 92 69 22 43 28 69 67 26 99 ...

output:

0
0
0
2
1
0
0
0
0
0
0
2
2
0
2
2
0
1
0
0
1
0
0
6
0
0
8
0
0
0
2
0
2
1
8
2
0
1
5
4
3
7
6
0
0
4
0
8
3
0
6
0
2
0
0
1
0
5
8
3
2
1
6
3
1
3
2
8
0
4
15
4
0
1
6
14
0
4
6
4
0
9
4
0
2
12
14
6
0
0
2
5
5
14
0
2
3
0
4
4
4
4
0
2
0
5
4
12
8
1
0
1
2
0
4
0
19
8
0
3
0
0
6
3
0
8
0
0
4
7
3
6
4
6
3
0
0
5
7
0
3
3
11
0
5
4
...

result:

ok 99999 lines

Test #109:

score: 84
Accepted
time: 85ms
memory: 6200kb

input:

100000
8237 26661 6461 11214 12127 13010 409 27730 22576 3378 743 2824 936 20257 18831 28661 28029 28627 20507 28139 17355 10192 25401 3635 5526 27164 3273 1847 24499 28949 15505 9087 1962 28317 26652 14088 17678 27060 11818 10253 6789 18912 13077 7725 9168 1907 6385 13549 6885 3244 11687 591 19787 ...

output:

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

result:

ok 99999 lines

Test #110:

score: 84
Accepted
time: 24ms
memory: 6280kb

input:

100000
219 192 299 107 123 174 235 7 97 176 45 32 225 56 238 247 193 273 291 141 72 183 244 286 150 192 96 35 127 38 115 45 229 165 203 103 90 189 110 187 64 206 270 41 261 207 287 153 231 277 46 3 211 289 288 113 180 83 199 6 173 13 102 101 177 4 204 19 192 65 205 8 270 226 48 282 184 86 187 115 11...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #111:

score: 84
Accepted
time: 32ms
memory: 7016kb

input:

100000
1 9463 98236 79629 45555 14348 95515 67155 198 82793 83884 26913 63185 18671 79026 3769 86757 84076 79788 46182 1388 45981 4209 43593 68247 63639 51233 87009 87157 48784 34327 39477 115 79523 37092 18794 18979 7615 30972 55624 70878 57105 98175 94303 999 48146 82371 36943 78390 93915 39030 56...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #112:

score: 84
Accepted
time: 30ms
memory: 6940kb

input:

100000
286 199 250 27 193 254 37 129 225 128 189 94 295 149 244 254 26 180 212 73 21 266 57 226 233 186 178 101 160 90 215 198 40 216 224 233 221 261 113 198 140 53 291 135 201 286 140 279 165 104 103 237 69 159 214 1 44 143 154 255 232 120 204 24 88 128 8 8 140 120 205 31 225 247 217 177 232 57 155...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #113:

score: 84
Accepted
time: 31ms
memory: 6396kb

input:

100000
132 285 201 156 18 199 101 63 188 145 292 184 33 56 86 272 139 181 208 151 88 99 62 16 148 250 140 292 178 273 16 9 9 268 216 27 218 16 141 106 212 184 289 297 240 126 268 78 7 175 280 94 25 41 161 173 290 52 164 219 77 231 279 85 250 194 163 220 261 3 25 173 187 65 169 178 191 188 255 197 63...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #114:

score: 84
Accepted
time: 118ms
memory: 6676kb

input:

100000
1 32285 96541 88209 78248 51801 19134 19178 84376 14311 29455 69614 8659 23099 52289 85314 62966 31006 94032 76042 32068 55258 66451 2053 69025 73205 6100 56234 82903 16923 91843 17256 83047 57584 85967 66224 58271 92061 66559 89109 70232 57506 97800 76725 57290 44768 32800 88681 88587 33366 ...

output:

0
0
1
1
1
1
3
3
3
3
3
3
3
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15
...

result:

ok 99999 lines

Test #115:

score: 84
Accepted
time: 136ms
memory: 5980kb

input:

100000
1 181 254 178 3 257 79 281 289 229 102 240 209 24 31 263 141 160 163 117 84 211 5 121 130 220 280 180 150 205 43 203 137 48 80 139 57 158 171 45 138 272 36 46 48 66 60 188 277 223 56 61 133 61 233 262 32 212 193 182 116 288 136 252 35 215 142 143 124 12 187 261 36 223 58 83 40 117 270 17 91 2...

output:

0
0
0
1
0
1
2
2
1
2
2
2
1
2
4
6
3
3
3
5
2
3
1
1
0
2
1
3
5
3
5
3
2
7
4
3
5
6
4
6
6
6
4
5
4
3
2
4
2
3
9
6
5
6
6
7
5
6
6
9
5
4
7
10
5
6
7
4
5
5
6
10
9
13
11
12
7
9
10
8
5
6
5
8
5
4
5
9
4
9
11
10
9
4
8
7
9
12
9
6
6
5
2
1
3
4
2
5
3
5
11
8
10
11
12
12
7
7
6
3
4
7
10
7
13
7
14
10
6
15
15
11
10
13
10
8
4
8
...

result:

ok 99999 lines

Test #116:

score: 84
Accepted
time: 52ms
memory: 6160kb

input:

100000
170 129 219 252 272 298 155 107 20 189 134 122 135 31 171 162 54 44 148 234 163 220 106 272 195 237 15 215 39 257 212 261 85 182 264 108 180 118 267 251 7 100 72 141 182 242 54 288 37 254 221 251 173 79 223 67 67 237 34 106 245 245 66 30 178 29 189 57 198 155 7 204 6 130 96 188 71 202 175 160...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #117:

score: 84
Accepted
time: 40ms
memory: 6772kb

input:

100000
228817 609583 745319 793620 471435 887525 770458 297733 141907 313852 184285 290211 513596 138986 14523 285904 418775 396544 643641 448555 552632 543401 475177 309656 874019 450448 730656 939056 182927 513777 86375 411743 123359 348046 721714 111145 235570 492171 925229 893828 322375 109513 7...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #118:

score: 84
Accepted
time: 37ms
memory: 6888kb

input:

100000
888693 177716 873244 955523 297193 582906 187670 526383 318275 414265 956176 715280 354791 355943 128422 321965 404354 799400 488421 916945 932154 399631 112201 537111 899126 258457 26036 634922 363321 330074 690065 252013 507789 79660 207535 321333 662565 911556 364067 980840 842173 320242 6...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #119:

score: 84
Accepted
time: 38ms
memory: 6324kb

input:

100000
380410 724075 994743 800266 500992 819717 750220 780716 123976 472025 169768 817340 718909 995611 942552 118183 890089 914018 492995 783309 402562 660529 10972 58391 500799 314090 138183 449261 520410 991822 768122 417171 232248 279216 733788 733240 98932 484007 30307 739260 956032 200074 556...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #120:

score: 84
Accepted
time: 30ms
memory: 6028kb

input:

100000
184 138 80 102 113 21 209 8 141 120 207 253 93 220 7 30 263 212 60 74 252 72 195 209 253 198 140 115 233 49 42 116 238 121 269 50 193 178 57 86 49 15 90 193 235 96 274 249 7 34 22 10 105 268 219 109 165 110 276 149 158 17 264 95 189 285 144 82 214 253 167 14 267 256 206 253 51 232 201 110 265...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #121:

score: 84
Accepted
time: 34ms
memory: 6016kb

input:

100000
159 10 214 198 147 249 293 86 66 104 164 265 271 275 271 28 266 265 230 75 104 127 166 230 126 132 68 247 31 163 246 189 172 159 139 70 160 183 155 225 286 71 241 256 97 264 36 114 228 265 188 83 144 105 12 269 289 132 267 71 294 212 260 217 123 150 38 282 32 245 258 70 15 198 77 163 161 112 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #122:

score: 84
Accepted
time: 29ms
memory: 6040kb

input:

100000
152 109 275 59 108 11 48 54 124 230 250 293 232 241 159 249 163 65 61 9 130 251 102 123 80 82 144 88 78 18 55 229 127 81 288 286 92 87 40 215 16 289 259 300 281 117 248 144 181 61 152 10 11 5 184 142 87 27 281 216 97 35 196 223 116 235 260 207 22 299 121 89 39 79 88 20 247 88 215 128 148 66 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #123:

score: 84
Accepted
time: 60ms
memory: 6668kb

input:

100000
920781 327996 137639 878789 665958 522963 783026 496527 496687 427667 471291 433486 874129 742005 584227 41002 394583 546636 518087 49137 356372 363406 76312 645579 239551 413839 972039 534565 177085 165402 453624 97866 493397 107614 493006 675707 146928 792383 172233 159967 220049 643523 593...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #124:

score: 84
Accepted
time: 66ms
memory: 6432kb

input:

100000
640954 594167 574526 973875 876215 193729 492498 585247 179978 541616 131874 404995 870735 633379 178320 561503 994086 528591 190729 456659 800076 592203 155434 841237 251820 858052 946363 215346 572727 504948 808498 730033 99114 899375 703907 491681 609455 712756 76927 305784 254371 725152 2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #125:

score: 84
Accepted
time: 62ms
memory: 6776kb

input:

100000
460112 610615 538673 880094 750868 403103 362465 479037 267923 182268 994185 385548 208817 636937 145192 21604 651388 420629 244680 20869 830684 732651 452532 103108 84401 236027 177725 674272 824150 17544 198938 800613 628158 253963 680706 895377 173417 559522 890766 441339 258141 884950 343...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #126:

score: 84
Accepted
time: 53ms
memory: 6580kb

input:

100000
277 15 241 156 137 165 130 120 149 165 73 266 122 249 194 150 255 58 81 208 148 284 254 222 98 241 258 211 276 113 249 4 179 242 160 67 106 41 187 6 205 11 271 79 11 216 280 265 26 112 172 173 95 177 94 193 118 103 103 145 215 103 149 146 44 60 212 202 100 150 207 57 161 230 135 171 145 166 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #127:

score: 84
Accepted
time: 47ms
memory: 6340kb

input:

100000
209 66 204 223 153 135 300 101 162 20 20 142 27 59 66 81 187 209 138 97 103 88 30 251 119 248 55 178 121 2 83 29 119 38 251 271 172 2 123 85 21 143 278 99 253 44 231 191 4 69 287 158 156 16 108 275 15 215 152 135 216 286 215 35 24 217 57 247 218 232 32 290 126 9 88 78 104 70 268 160 138 6 17 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Test #128:

score: 84
Accepted
time: 50ms
memory: 6780kb

input:

100000
198 26 289 127 160 258 176 263 87 228 203 142 264 170 161 146 204 272 233 252 256 263 279 203 158 73 235 283 193 52 88 91 77 76 217 236 33 144 198 120 71 152 261 86 74 173 231 29 145 216 281 152 178 11 54 88 84 288 70 28 40 157 170 168 232 138 156 264 281 53 135 52 257 148 189 30 72 172 58 26...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99999 lines

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-11-29 06:34:29 | OpenSource Project