QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#313444#8127. Slučajna CestaCrysfly40 156ms38768kbC++172.5kb2024-01-24 19:20:052024-01-24 19:20:05

Judging History

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

  • [2024-01-24 19:20:05]
  • 评测
  • 测评结果:40
  • 用时:156ms
  • 内存:38768kb
  • [2024-01-24 19:20:05]
  • 提交

answer

// what is matter? never mind.
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define mod 1000000007
struct modint{
	int x;
	modint(int o=0){x=o;}
	modint &operator = (int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
	modint &operator ^=(int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	friend modint operator +(modint a,modint b){return a+=b;}
	friend modint operator -(modint a,modint b){return a-=b;}
	friend modint operator *(modint a,modint b){return a*=b;}
	friend modint operator /(modint a,modint b){return a/=b;}
	friend modint operator ^(modint a,int b){return a^=b;}
	friend bool operator ==(modint a,modint b){return a.x==b.x;}
	friend bool operator !=(modint a,modint b){return a.x!=b.x;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}

vector<modint> fac,ifac,iv;
inline void initC(int n)
{
	if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
	int m=iv.size(); ++n;
	if(m>=n)return;
	iv.resize(n),fac.resize(n),ifac.resize(n);
	For(i,m,n-1){
		iv[i]=iv[mod%i]*(mod-mod/i);
		fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
	}
}
inline modint C(int n,int m){
	if(m<0||n<m)return 0;
	return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
 
#define maxn 1000005
#define inf 0x3f3f3f3f

int n,fa[maxn];
modint a[maxn],f[maxn];
vi e[maxn];

modint dfs(int u,int pa)
{
	int cnt=0;
	modint sum=0;
	for(int v:e[u]){
		if(v==pa)continue;
		modint w=dfs(v,u);
		cnt+=1;
		sum+=w;
	}
	modint res=(1-qpow((mod+1)/2,cnt));
	res*=sum/cnt;
//	cout<<"res "<<res.x<<"\n";
	res+=a[u];
	return res;
}

signed main()
{
	n=read();
	For(i,2,n)fa[i]=read(),e[fa[i]].pb(i),e[i].pb(fa[i]);
	For(i,1,n)a[i]=read();
	For(i,1,n)cout<<dfs(i,0).x<<"\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 34956kb

input:

2
1
307903 536004

output:

575905
500689959

result:

ok all correct

Test #2:

score: 10
Accepted
time: 0ms
memory: 35104kb

input:

3
1 2
992649 690492 637324

output:

1497226
876301738
251230734

result:

ok all correct

Test #3:

score: 10
Accepted
time: 4ms
memory: 35780kb

input:

4
1 2 3
826918 524416 30987 233038

output:

501126006
889825
375470082
250483002

result:

ok all correct

Test #4:

score: 10
Accepted
time: 4ms
memory: 36580kb

input:

5
1 2 3 4
859332 957641 552087 294350 114098

output:

126520100
939052817
751204107
938304296
125572709

result:

ok all correct

Test #5:

score: 10
Accepted
time: 5ms
memory: 36276kb

input:

6
1 2 2 4 5
91742 92552 191745 529457 181043 884683

output:

47206686
156670572
984787945
922712805
617936136
829257432

result:

ok all correct

Test #6:

score: 10
Accepted
time: 0ms
memory: 34916kb

input:

7
1 1 3 4 4 6
69032 207537 280790 889967 218886 618588 754535

output:

293473187
945792944
24287651
511768034
204044442
255223945
87278766

result:

ok all correct

Test #7:

score: 10
Accepted
time: 6ms
memory: 38768kb

input:

8
1 2 2 4 2 6 7
546075 347525 670520 983062 581593 336046 97830 706738

output:

334418635
329187863
605358267
243713478
246081337
164970462
770221487
347328072

result:

ok all correct

Test #8:

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

input:

9
1 2 3 3 5 1 7 8
817515 848951 198209 119142 819728 367379 501231 458709 804045

output:

778945070
884374888
701481221
254592128
137000383
674805839
311894676
750233527
417348933

result:

ok all correct

Test #9:

score: 10
Accepted
time: 4ms
memory: 34908kb

input:

10
1 1 1 4 5 4 1 8 8
874755 324368 592836 600006 266724 217696 423188 402322 557734 423393

output:

616715460
217237546
634133532
688080628
590912992
60727477
121167098
530612063
430789154
868180005

result:

ok all correct

Test #10:

score: 10
Accepted
time: 0ms
memory: 35764kb

input:

10
1 2 3 1 5 6 7 7 9
195744 206104 723327 114978 178292 190130 540646 250919 152931 940237

output:

158806482
79765837
290477198
526950480
317003915
633487763
313413032
531963588
860175194
157463149

result:

ok all correct

Test #11:

score: 10
Accepted
time: 4ms
memory: 36628kb

input:

10
1 2 2 4 5 4 7 1 9
160335 133086 186701 906673 561321 529327 813569 759454 327734 62760

output:

612909843
659626152
629535210
48467043
569673492
130085768
77772881
52282583
56718813
704471661

result:

ok all correct

Test #12:

score: 10
Accepted
time: 0ms
memory: 36876kb

input:

10
1 2 2 1 5 6 7 8 9
286342 884910 904819 108098 292165 78969 566381 587683 156711 111976

output:

821283130
567751781
374520609
61373271
149275061
51484565
229512794
771472918
448321820
132272409

result:

ok all correct

Test #13:

score: 10
Accepted
time: 9ms
memory: 35120kb

input:

10
1 1 3 3 5 6 6 6 9
820907 494966 187493 466984 150135 896410 388758 105418 191024 930665

output:

363066644
242278836
612403907
108326578
274335852
819650079
613004775
29429418
811535270
291689673

result:

ok all correct

Test #14:

score: 10
Accepted
time: 4ms
memory: 34924kb

input:

10
1 2 3 4 5 5 7 7 9
780617 360476 946142 170041 984436 863484 705401 759288 364152 323780

output:

792343871
562727727
562167115
91166936
840366602
290796618
770432943
924365902
661973330
774831032

result:

ok all correct

Test #15:

score: 10
Accepted
time: 9ms
memory: 35644kb

input:

10
1 2 2 1 5 5 1 1 9
996177 507917 928080 610241 428655 745973 313129 879790 3630 222636

output:

585661496
324752716
780879684
93121435
366439393
584327336
833975652
801152444
944125266
629583216

result:

ok all correct

Test #16:

score: 10
Accepted
time: 0ms
memory: 35780kb

input:

10
1 2 3 4 5 6 7 8 9
485357 872875 543104 252486 738854 873509 801028 59862 417026 867486

output:

739460169
733862443
778669222
462141515
876563208
978255004
317930623
65403099
345776883
397765700

result:

ok all correct

Test #17:

score: 10
Accepted
time: 0ms
memory: 34868kb

input:

10
1 1 3 1 5 6 6 8 5
405829 249733 974377 17147 381677 349987 698528 659718 383030 547497

output:

828512375
738117175
280840778
603744319
264086975
110768674
214583133
895570339
763890880
911231948

result:

ok all correct

Test #18:

score: 10
Accepted
time: 9ms
memory: 35412kb

input:

10
1 2 3 1 5 6 7 8 7
114148 888405 653482 324506 212949 908169 155568 180096 181076 166389

output:

809474092
686924034
656473190
604449927
836836772
782500753
768863726
321788284
881297985
199739646

result:

ok all correct

Test #19:

score: 10
Accepted
time: 0ms
memory: 34900kb

input:

10
1 1 3 4 5 6 7 6 9
878639 541255 25599 274902 119473 639010 97108 753448 96106 773930

output:

983622610
739341242
903019368
274169390
281959300
123432644
720471011
147529573
361101388
741298692

result:

ok all correct

Test #20:

score: 10
Accepted
time: 9ms
memory: 36052kb

input:

10
1 2 2 2 2 2 2 2 2
766887 885978 73938 216251 903006 615990 205756 890530 603065 506057

output:

671137547
284402329
811845161
839566505
932739803
157080025
982378930
332142162
366784703
464349985

result:

ok all correct

Test #21:

score: 10
Accepted
time: 0ms
memory: 36716kb

input:

10
1 2 3 4 5 6 7 8 9
733342 202778 673543 829195 415681 35504 602267 386331 559518 466392

output:

735524386
852512262
329450881
470194237
94855921
266434302
571422189
161172655
331123819
887672425

result:

ok all correct

Test #22:

score: 10
Accepted
time: 0ms
memory: 36684kb

input:

10
1 2 2 1 4 4 6 3 8
904213 323773 607336 184293 233574 392314 370246 454542 257726 448337

output:

590656244
75229314
856033476
756000651
60461972
354421829
289846343
833907290
404114388
639532023

result:

ok all correct

Subtask #2:

score: 30
Accepted

Test #23:

score: 30
Accepted
time: 10ms
memory: 35436kb

input:

100
1 2 1 4 5 6 7 7 9 9 5 12 5 4 1 16 17 18 18 20 20 22 23 24 25 23 27 28 27 30 31 32 27 34 35 36 37 38 39 39 41 38 43 43 45 46 43 48 49 49 49 48 48 54 55 56 57 57 55 60 60 62 55 64 65 64 67 67 69 69 69 72 37 74 75 76 76 78 76 80 81 82 80 84 85 74 87 87 89 89 91 89 87 94 94 96 97 98 98
754341 720186...

output:

744419112
868534785
579276734
966426530
89470157
365627670
936462279
93017671
603359319
522390035
22343082
205462129
636979071
211558039
86006737
525095665
167727115
994038924
460586504
309146514
877389799
199845255
163729135
868507823
372639715
82379059
856574083
348017654
982070262
781505719
17297...

result:

ok all correct

Test #24:

score: 30
Accepted
time: 11ms
memory: 35292kb

input:

200
1 1 3 4 5 6 7 8 8 5 11 12 13 13 15 16 16 18 19 20 21 22 23 16 25 25 27 28 29 30 31 28 33 28 35 35 37 35 13 40 41 42 40 44 45 46 47 45 49 50 50 52 53 52 52 56 56 58 58 60 56 62 62 62 65 65 67 68 65 70 71 65 73 73 75 75 77 77 79 80 79 82 83 84 83 86 87 87 89 90 91 92 92 94 92 96 97 98 96 92 101 10...

output:

725084368
983709498
824961909
336358280
709426657
297523596
426557566
767786580
119003107
931503705
534694332
425258617
150579774
654744506
642042232
884679319
138214497
181144455
893410053
52582794
987525977
416233639
552678811
618456103
941998026
784721349
218719610
952238453
248625961
515894278
7...

result:

ok all correct

Test #25:

score: 30
Accepted
time: 19ms
memory: 35424kb

input:

300
1 1 3 3 5 6 7 8 9 10 10 12 13 13 15 15 15 18 19 18 21 22 23 24 25 26 26 28 29 29 31 32 33 34 31 36 36 36 39 24 41 42 41 44 44 46 46 48 49 50 51 52 51 48 55 56 57 57 57 56 61 62 63 63 65 65 67 68 65 70 65 72 73 74 73 76 76 78 79 80 81 82 83 84 84 86 86 81 89 90 90 92 90 94 95 95 97 97 99 99 101 1...

output:

245228535
330574102
623747432
347404985
841330143
377311095
101979551
376122688
338441219
182393713
197828758
67681752
944133369
483788933
74252544
239292125
10620946
809868775
90567869
977253962
373790456
974815708
812859891
573734099
770042308
506972531
441953277
671648793
804831163
642858219
5873...

result:

ok all correct

Test #26:

score: 30
Accepted
time: 27ms
memory: 34956kb

input:

400
1 2 2 4 4 6 7 7 9 9 11 12 12 14 15 16 17 18 19 20 17 22 22 24 6 26 27 27 29 30 31 32 31 34 35 31 27 38 38 40 41 42 43 44 43 46 47 48 49 50 51 51 50 54 54 56 57 56 59 60 60 62 60 64 65 64 64 49 69 70 70 72 73 74 70 69 77 78 79 80 43 82 82 84 82 86 87 86 89 82 91 92 93 94 94 96 97 96 99 100 94 102...

output:

754332851
602516582
858960349
394861150
370101800
818086925
381161276
772456843
533357677
923445686
533256367
446071355
358631457
792990398
767235134
374957506
563570675
39871177
770504510
886075159
591304517
272762925
568365410
973459255
815692541
497998120
151711203
35325302
537107679
467417192
52...

result:

ok all correct

Test #27:

score: 30
Accepted
time: 38ms
memory: 36120kb

input:

500
1 1 3 4 4 6 7 8 7 10 11 11 10 14 15 15 17 18 19 20 21 22 20 20 15 26 1 28 29 28 31 31 33 33 35 36 37 38 39 40 41 42 41 44 45 45 45 48 48 50 51 51 53 54 54 45 57 57 45 35 61 62 62 64 64 66 67 68 66 66 71 72 73 74 75 76 76 76 79 79 71 82 83 84 83 83 87 87 89 90 90 90 90 66 95 96 97 95 99 33 101 10...

output:

906511411
413531698
745505573
641643624
662863268
401252230
595706839
42431125
362173724
700649975
179990748
187809670
187389614
670195856
817888726
179822185
318036156
415931158
221538951
759090116
79610140
321151639
964539521
517058362
600541445
486856458
241771164
885795312
751536190
334841583
31...

result:

ok all correct

Test #28:

score: 30
Accepted
time: 53ms
memory: 36848kb

input:

600
1 1 3 3 5 6 7 8 9 10 9 12 13 14 15 14 17 18 17 20 13 22 22 24 24 22 27 22 29 29 31 32 33 34 33 36 37 32 39 40 39 42 42 44 45 46 47 48 13 50 51 1 53 54 55 56 56 55 59 60 61 55 63 64 64 66 63 68 69 55 71 72 73 74 74 72 77 77 79 80 81 81 83 84 81 86 87 88 89 55 91 91 93 93 93 96 97 98 98 91 101 102...

output:

663139314
649624699
751037743
473869401
196678294
968269744
472882712
213799472
421260937
641073389
760627003
257912082
616548809
662549687
547402110
364876691
229947924
20337318
847324789
512030620
925329816
600788387
714887131
727246386
691159491
441218441
90415548
477248289
423098965
201224028
60...

result:

ok all correct

Test #29:

score: 30
Accepted
time: 71ms
memory: 36340kb

input:

700
1 2 2 4 1 6 6 8 8 6 11 12 13 12 11 16 17 17 19 20 21 22 21 24 25 25 27 28 29 30 30 30 25 34 35 34 37 38 17 17 41 41 43 44 43 46 47 48 49 50 47 52 41 41 55 56 57 58 59 60 57 62 63 64 64 66 66 68 62 70 70 72 55 74 75 76 76 78 79 80 78 82 83 84 83 86 87 88 88 90 91 90 93 90 78 96 97 98 97 100 101 1...

output:

570872379
237182013
688066
86834668
641516489
591491574
3158251
59233535
333219945
270152432
668422598
235996748
622223543
998639327
714391301
493516651
985359148
628204166
746819282
529690805
34279739
680252229
953391073
928607169
631197490
144333434
682858220
457488682
210043864
662617590
75057910...

result:

ok all correct

Test #30:

score: 30
Accepted
time: 98ms
memory: 35560kb

input:

800
1 2 3 4 4 6 7 4 9 10 11 11 11 2 15 16 16 18 19 19 19 19 23 23 25 23 27 28 29 30 31 32 30 34 35 34 34 34 39 19 41 41 43 41 45 41 47 48 49 48 48 52 47 54 16 56 56 58 59 59 61 61 63 64 65 63 67 68 69 68 67 72 73 61 75 76 77 77 76 80 81 82 83 84 85 86 84 88 88 90 83 92 81 94 95 96 97 81 99 100 101 9...

output:

233496187
599291184
479012731
855127161
401991189
274677969
418543687
362349277
577701995
828969207
816848399
495058149
328423591
78078113
161123890
815238539
473019428
878535442
18674067
835577888
463623498
897658423
213366930
848188502
542963887
862188865
584746388
174480342
100279923
173069394
96...

result:

ok all correct

Test #31:

score: 30
Accepted
time: 119ms
memory: 35688kb

input:

900
1 2 3 4 5 5 7 8 4 10 11 11 13 14 15 16 3 18 19 19 19 19 23 23 23 26 27 28 29 30 31 32 33 34 35 36 34 38 39 40 33 42 43 43 45 45 47 48 48 45 51 52 53 52 51 56 57 57 57 31 61 61 63 61 65 19 67 68 69 69 71 72 73 71 75 76 77 78 79 79 81 82 78 84 84 76 87 88 88 90 91 92 92 94 94 96 91 98 98 100 101 1...

output:

481422270
722211524
968944619
873430456
569340426
696897242
960672903
855860632
237528392
803883698
282053334
922373608
482232420
171159441
945594423
192483984
712235134
176120775
245350023
332340008
460005442
166307245
144798528
279179169
591618709
652685782
617304045
890361202
107606344
627358135
...

result:

ok all correct

Test #32:

score: 30
Accepted
time: 145ms
memory: 36332kb

input:

1000
1 2 2 4 1 6 7 8 6 1 11 11 13 14 15 16 15 11 19 1 21 22 23 24 24 26 27 28 28 1 31 32 33 32 32 36 32 31 39 1 41 42 43 43 45 42 41 48 49 1 51 52 52 51 55 51 57 58 59 1 61 62 62 64 62 66 67 66 69 1 71 71 73 74 75 76 77 78 79 1 81 82 82 84 82 86 87 87 89 1 91 91 93 94 95 95 97 98 97 1 101 102 103 10...

output:

860962935
342129626
68822226
457947417
472192430
663590072
528597324
421355230
30806031
980716344
775140697
855909014
685267513
433181261
645721034
637713641
91714280
996133261
790463317
277249991
361750689
880420626
88321325
560640892
48310409
106320979
749041052
477559724
289354988
414711535
70323...

result:

ok all correct

Test #33:

score: 30
Accepted
time: 145ms
memory: 36000kb

input:

990
1 1 1 1 5 6 7 6 9 9 1 12 12 14 12 16 17 18 19 18 21 1 23 23 25 25 27 28 28 30 31 31 1 34 34 36 36 38 39 40 41 34 43 1 45 46 47 48 49 50 50 48 53 53 1 56 56 58 58 60 61 62 63 63 62 1 67 68 68 68 71 71 73 74 75 73 1 78 78 80 80 80 83 80 85 85 87 1 89 90 89 89 93 94 93 96 96 96 1 100 101 101 103 10...

output:

566521970
19653884
957347745
785407324
95586701
595663598
610224234
823813619
540500089
776787780
651399838
54001866
445110629
76766067
968249950
791568580
802774970
111247619
471825425
147997418
565116118
210072282
451700816
317545773
814453618
488318872
555385352
116808350
807663467
714985382
4313...

result:

ok all correct

Test #34:

score: 30
Accepted
time: 147ms
memory: 35028kb

input:

996
1 2 3 4 5 6 5 3 9 9 9 1 13 14 15 13 17 18 13 20 21 20 23 1 25 25 27 28 29 30 31 31 33 33 25 1 37 37 39 40 40 42 42 42 45 46 45 1 49 50 51 50 53 54 55 56 54 58 53 1 61 61 63 61 65 66 66 68 61 70 71 1 73 74 73 76 76 78 79 78 81 82 82 1 85 86 87 87 89 90 90 90 89 94 95 1 97 98 99 99 98 98 103 104 1...

output:

748874153
262146514
794139762
417820957
298970407
382358247
5414946
103359054
855914104
123309747
81482823
101977388
92589265
523995204
605707038
320493045
125905537
969755207
63784176
441155209
154337970
20171151
114797496
410322060
50350007
762147631
420862102
377956803
22797731
429289375
49433594...

result:

ok all correct

Test #35:

score: 30
Accepted
time: 141ms
memory: 36268kb

input:

988
1 2 1 4 5 5 7 8 9 10 7 12 1 14 14 16 17 18 18 20 20 22 23 20 25 1 27 28 28 30 31 30 33 33 35 35 33 38 1 40 41 42 43 44 45 46 47 48 48 46 51 1 53 54 55 56 56 56 55 60 61 61 55 64 1 66 67 68 69 69 69 72 68 74 75 76 76 1 79 79 81 82 83 82 85 86 87 87 87 81 1 92 93 94 93 96 96 98 99 99 101 98 103 1 ...

output:

622685004
586644318
974784715
688575722
724649130
930489320
286767417
349766241
97171025
892488388
845049214
97843912
648810060
680152501
830749961
384209943
442923008
438908715
77100762
156169586
199275646
340907539
327084666
635293813
94536865
980218063
136570259
412676747
59973487
504052430
89769...

result:

ok all correct

Test #36:

score: 30
Accepted
time: 147ms
memory: 36700kb

input:

994
1 1 1 4 1 6 7 1 9 9 11 9 13 1 15 15 15 18 19 20 21 22 23 23 25 26 23 1 29 30 31 31 30 34 35 35 37 38 37 40 40 1 43 44 45 46 45 48 49 50 48 44 53 53 55 1 57 58 59 59 61 62 62 64 64 64 67 68 68 1 71 71 73 74 75 74 71 78 79 79 79 82 71 1 85 86 87 88 89 89 91 87 93 94 93 96 93 1 99 100 100 99 103 99...

output:

351906097
418196456
800116970
230924268
487732224
705400952
727810098
485486331
666494686
397372093
305762969
787863087
688737733
792978069
238014934
225927280
601615032
113511344
195873644
875314471
991863898
854453158
970927848
217035938
171182939
23494103
849454215
967280867
580937409
725333795
5...

result:

ok all correct

Test #37:

score: 30
Accepted
time: 141ms
memory: 36592kb

input:

990
1 1 3 3 5 6 7 8 9 6 11 12 13 12 1 16 17 18 18 20 20 22 23 22 25 25 25 28 29 1 31 32 32 32 35 36 35 38 35 40 41 42 41 44 1 46 46 48 49 50 51 52 48 54 55 55 57 57 48 1 61 61 63 64 65 66 67 66 69 70 65 72 73 72 1 76 76 78 79 80 81 82 78 84 85 78 87 87 89 1 91 92 91 94 95 95 97 98 95 100 100 102 103...

output:

171716349
826522197
827435960
246212111
496792282
831079660
507730844
942351412
846775580
231804575
612122929
222863497
705101267
386790628
553867612
357863959
754836419
28499939
464916813
916106291
187482558
949079915
316083445
294612216
836187764
655471514
842762710
355196854
709326425
222955504
8...

result:

ok all correct

Test #38:

score: 30
Accepted
time: 146ms
memory: 36476kb

input:

992
1 2 3 2 5 6 7 7 9 10 11 6 6 14 15 1 17 18 17 20 21 22 22 24 25 25 27 28 28 30 31 1 33 34 35 35 35 38 34 40 41 42 43 44 44 41 47 1 49 50 51 52 51 54 55 55 57 58 50 60 60 62 60 1 65 65 67 68 68 68 67 72 73 74 74 72 77 78 79 1 81 81 83 83 85 85 83 88 88 90 91 91 93 94 94 1 97 98 99 98 101 98 103 10...

output:

505943433
85278950
560248446
123470514
437750030
15710952
374500091
134365778
798108989
71698259
630177235
336715186
859789293
844790277
766492557
760998581
579309950
938348690
459037263
595363866
886814495
877183620
662048691
413415159
491837538
13315517
332259090
816351110
721503013
654603103
6712...

result:

ok all correct

Test #39:

score: 30
Accepted
time: 141ms
memory: 35264kb

input:

986
1 2 3 3 3 6 7 7 9 10 11 12 13 14 15 15 1 18 19 20 21 21 23 24 23 26 27 28 29 30 29 29 33 1 35 36 37 38 39 39 41 42 43 44 45 43 41 48 49 38 1 52 53 54 55 55 57 58 54 60 53 62 63 63 65 66 67 1 69 70 70 72 73 74 69 76 77 78 78 77 81 81 83 84 1 86 87 86 89 89 91 91 93 89 95 96 97 98 99 100 99 1 103 ...

output:

789218245
501848982
616046947
7000199
111177722
792623975
99891325
501768858
58464812
125064003
753684990
9085891
518545750
537283672
172606342
397255357
959173940
521699802
734185616
63210187
673894123
826131873
97288984
950373989
717039561
852849498
943754388
255730130
288272653
452945492
13579873...

result:

ok all correct

Test #40:

score: 30
Accepted
time: 150ms
memory: 36896kb

input:

990
1 2 3 3 1 6 7 7 7 10 11 12 12 14 7 16 16 1 19 19 19 22 23 23 25 23 27 28 28 27 31 32 32 32 35 1 37 38 38 40 41 37 43 44 45 46 47 46 46 50 51 51 53 1 55 56 56 56 59 60 59 56 63 64 65 66 67 68 69 68 71 1 73 73 75 76 77 77 73 80 80 80 80 84 84 86 86 86 86 1 91 92 93 94 95 94 97 94 99 100 100 102 10...

output:

347724386
434953828
278379318
277331845
214728081
610771529
6158178
838493203
752649405
625546702
705897575
258707468
952282066
940915211
211291782
175806819
309481836
121859538
701774437
345330893
32778931
124956075
497611432
957345086
483506862
155977179
86311048
54252523
446246284
8728605
5984218...

result:

ok all correct

Test #41:

score: 30
Accepted
time: 142ms
memory: 36272kb

input:

988
1 1 1 4 5 6 5 8 9 9 11 12 12 14 11 16 16 18 1 20 21 22 20 24 24 26 27 28 29 30 31 28 33 34 35 33 37 1 39 39 41 39 43 44 45 46 47 48 49 48 51 52 53 53 55 53 1 58 59 60 61 62 63 64 65 63 67 67 69 60 71 71 58 74 75 1 77 78 79 80 81 81 83 78 85 86 86 85 89 89 91 89 93 78 1 96 96 96 99 100 99 102 102...

output:

295346165
798770696
510413103
82785149
669919735
422081782
948196683
916989932
985940742
661260859
833440490
649736170
623252181
421209122
281291550
934402632
181083043
878638266
169498577
514714462
123035459
780926980
104155817
260206869
15540268
641771435
877529821
888185756
834604198
886452595
13...

result:

ok all correct

Test #42:

score: 30
Accepted
time: 143ms
memory: 36400kb

input:

1000
1 2 3 2 5 5 7 1 6 4 11 3 9 4 7 13 14 17 18 15 18 8 6 10 17 22 10 19 11 25 29 27 30 24 21 24 23 13 16 9 14 12 35 38 8 32 40 33 12 35 41 36 33 22 29 43 42 19 37 56 61 21 27 62 32 62 48 37 57 54 36 56 52 60 52 71 42 44 75 66 51 82 45 65 44 48 87 55 51 78 23 30 68 58 78 89 96 43 86 97 34 49 83 25 8...

output:

687945387
546383013
463784605
247575625
486788744
62343156
665815813
67847197
55185459
824173197
162695259
242054167
663563775
763117213
593920999
79360217
317731608
531031619
40724107
725867357
226274624
810222907
44373511
39379307
572995347
713209541
930765550
234054701
878624249
496121150
4119486...

result:

ok all correct

Test #43:

score: 30
Accepted
time: 148ms
memory: 36544kb

input:

1000
1 1 3 3 2 6 2 6 9 4 8 5 9 7 8 16 14 13 4 19 21 14 17 11 19 18 16 24 24 7 13 15 12 29 28 12 35 22 27 33 22 21 43 26 43 26 47 10 45 10 39 42 34 49 47 49 41 42 25 20 23 53 39 41 30 40 33 38 27 48 30 56 18 44 69 68 75 48 51 73 59 37 40 78 37 69 70 82 85 31 36 52 77 89 34 94 94 57 85 63 20 101 63 58...

output:

509639546
447230120
270271799
999513991
211596126
429563279
957584143
568844413
868522798
534386729
473218386
660177319
649956576
1526408
703544068
195817016
207805950
617740539
647080663
491157853
830085182
701022021
879195878
900000706
864193753
383201443
258728349
836786103
371782725
173986990
76...

result:

ok all correct

Test #44:

score: 30
Accepted
time: 156ms
memory: 35724kb

input:

1000
1 1 2 3 2 4 7 7 8 4 3 6 13 11 10 10 14 5 19 14 13 19 6 5 16 21 12 16 21 29 29 11 33 24 34 35 17 8 18 22 30 22 31 44 28 37 35 32 47 15 51 28 12 31 25 38 37 32 58 57 49 52 61 47 18 34 26 27 43 36 44 71 54 42 49 24 30 39 71 40 55 73 77 79 45 80 20 74 25 66 20 9 15 65 72 83 68 50 68 77 62 102 55 62...

output:

580578034
924246152
913399538
703655322
984158
301660688
697315862
993744950
156424374
485299106
809681185
678482784
538154743
869312897
121977664
940019480
570631749
662384090
975333965
477959769
892825183
597127681
867493058
331326215
974820246
714441040
243600775
465464397
109308308
270486564
480...

result:

ok all correct

Test #45:

score: 30
Accepted
time: 150ms
memory: 36276kb

input:

1000
1 1 3 4 2 6 7 8 3 8 9 12 11 12 4 7 14 14 13 5 2 11 13 5 25 22 16 21 22 21 10 10 26 28 25 36 18 33 27 30 24 20 26 41 27 36 31 39 46 30 39 38 29 31 42 37 33 17 29 38 6 54 54 44 20 40 47 35 56 34 57 43 9 51 67 44 64 34 55 23 58 58 15 17 82 80 73 85 47 68 80 42 81 86 75 92 87 82 83 49 68 52 23 53 8...

output:

125093706
704739815
102083849
279307769
271258078
819936910
620508746
524442890
554584666
782450571
434528173
70403377
827932445
964312269
816262054
884778219
414025116
785799824
324367831
124151976
275394760
34724066
550144093
522437131
300633676
423178949
330589144
838103761
434323011
69245398
998...

result:

ok all correct

Test #46:

score: 30
Accepted
time: 150ms
memory: 36668kb

input:

1000
1 1 2 4 5 3 7 4 8 3 5 8 10 13 14 7 12 17 19 14 15 20 23 2 9 10 26 21 21 12 23 13 25 15 25 31 17 27 24 31 6 18 32 37 40 26 29 37 39 27 29 16 20 24 32 56 36 22 19 40 47 58 45 58 35 63 38 44 65 33 34 51 69 47 74 62 48 64 72 30 70 70 61 34 52 84 50 60 62 35 85 51 65 38 64 72 52 6 73 16 49 43 94 41 ...

output:

423889453
363861048
59128790
972909604
755594617
397299818
49744452
864548563
216668395
433199925
542401571
362740165
484236228
28452270
283123170
578429970
716917589
261218228
693965878
453694984
667100806
203273997
829932215
657244822
196827637
599090703
559389359
741241575
249277413
612231321
194...

result:

ok all correct

Test #47:

score: 30
Accepted
time: 145ms
memory: 35136kb

input:

1000
1 1 3 3 5 5 7 8 8 10 10 12 8 8 15 16 17 18 18 20 21 17 23 24 24 26 7 28 29 28 31 32 32 34 35 36 36 36 39 39 41 42 43 44 45 46 43 48 49 49 49 52 53 49 55 56 57 57 59 57 61 62 62 64 65 66 67 68 67 70 71 72 73 74 74 64 77 49 79 80 81 82 82 84 82 86 87 88 86 90 91 92 93 93 95 96 97 97 99 100 99 102...

output:

588909236
809333062
274232845
649764930
862786045
331745643
19377577
149964644
632538200
798978725
567371111
527404637
268681708
663945980
75749893
422819549
565554395
116891266
468347509
898265341
324742101
883623856
412322600
365213634
637175795
954270110
53007126
376535767
78875956
303151737
7531...

result:

ok all correct

Test #48:

score: 30
Accepted
time: 149ms
memory: 34884kb

input:

1000
1 2 3 4 5 5 2 8 9 8 11 11 13 14 15 14 17 1 19 20 21 21 20 20 25 25 27 28 20 30 30 20 33 34 34 36 37 38 37 40 41 33 43 43 43 46 47 48 49 43 51 52 52 51 55 56 57 58 58 57 61 62 63 57 65 65 67 65 69 70 69 72 72 74 74 76 76 78 76 80 81 82 72 84 84 86 84 88 89 90 89 92 93 94 92 96 96 98 99 100 99 10...

output:

446128953
771846193
353581030
641992303
282359178
172760761
110824105
210873333
164551930
443644297
500282360
759533350
151181150
677005730
782470503
521521232
922591322
115341649
935429532
321221849
554037403
258492425
70923362
624831335
441181533
444773520
998121344
437321692
791730488
72633192
85...

result:

ok all correct

Test #49:

score: 30
Accepted
time: 147ms
memory: 36220kb

input:

1000
1 2 1 4 5 6 7 7 9 10 9 4 13 14 15 16 17 17 17 20 21 21 23 24 25 25 21 28 29 30 31 29 33 17 35 35 37 38 39 40 40 42 42 44 44 38 14 48 48 50 51 52 53 52 55 56 57 52 59 60 59 62 63 64 62 66 67 66 69 69 71 72 73 73 73 76 77 77 79 80 81 82 83 84 85 86 84 88 89 90 88 88 93 88 95 96 96 98 99 100 99 98...

output:

654471914
546615139
947922048
153503048
927630717
34223875
720388683
624306296
655456589
493083987
162073331
635838124
369929303
821333236
550440341
545680814
718752631
583115422
974066149
970294098
83094502
529671142
926147748
440592283
656733466
993666437
369100852
386989615
894289686
451198654
81...

result:

ok all correct

Test #50:

score: 30
Accepted
time: 145ms
memory: 36032kb

input:

1000
1 2 1 4 4 6 6 8 9 10 11 12 12 9 15 8 17 1 19 20 21 21 23 21 19 26 26 28 29 30 26 32 33 34 35 36 36 38 39 38 32 42 43 43 45 42 47 47 49 50 50 26 53 53 53 56 57 56 56 60 61 61 63 64 65 66 66 68 68 70 71 72 72 68 75 76 77 77 79 80 81 82 79 79 85 86 87 65 89 89 91 92 93 89 95 96 95 98 98 100 98 102...

output:

273532484
654900746
436901865
756951444
254519896
330002995
766044403
657460442
745446314
216201924
409558282
471338773
294275946
357142440
886431363
257567760
860256462
73649121
723536403
211807232
756732344
440886399
34106368
189767637
336626138
626005472
417874102
19728680
729174453
552154932
534...

result:

ok all correct

Test #51:

score: 30
Accepted
time: 146ms
memory: 36660kb

input:

1000
1 2 2 4 5 4 7 8 9 10 9 9 13 14 15 14 17 18 19 20 21 21 23 23 25 23 27 28 29 30 30 32 32 32 35 36 37 38 36 35 41 42 42 28 21 46 47 48 48 46 51 52 53 53 55 8 57 58 59 60 59 62 58 64 65 66 67 67 69 69 69 69 73 73 75 76 77 78 78 80 81 82 83 84 85 85 69 65 89 89 89 92 93 92 95 92 97 98 97 100 101 10...

output:

725195196
613825412
600466575
988748057
848020147
898988028
894024440
812375964
126387118
12947424
758813173
48614630
831378166
501730144
518516178
262917238
636605147
339884843
211964574
439677203
686412818
944085138
603580837
5265397
777691070
602160082
70957755
414236280
230808563
310343986
28932...

result:

ok all correct

Test #52:

score: 30
Accepted
time: 153ms
memory: 35252kb

input:

1000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

output:

313566704
94576682
1320726
907941445
266980443
9723392
6237132
506086800
508113157
513847305
276737286
926631954
539407134
921768459
514471445
113377640
768934724
558859508
128223730
510892069
648378489
108521218
373281868
323396513
185226376
389161363
37575819
453296146
345134729
159169406
51433570...

result:

ok all correct

Test #53:

score: 30
Accepted
time: 145ms
memory: 35956kb

input:

1000
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

output:

908125419
945014005
688802237
69758801
690902928
728264629
497206206
758219731
743444429
834292230
94670858
192305546
567678971
33262989
936582856
84809030
931316352
956530676
703737368
950055104
464254266
694273301
874304574
11822831
683439534
180219586
868835018
32164593
42017275
855077189
5708268...

result:

ok all correct

Subtask #3:

score: 0
Time Limit Exceeded

Test #54:

score: 0
Time Limit Exceeded

input:

60000
1 2 2 1 3 4 5 6 9 6 11 11 13 8 4 10 7 10 3 16 12 9 19 15 24 24 27 25 8 16 13 7 20 15 22 28 33 31 20 27 41 17 25 35 39 5 22 34 19 14 49 34 51 31 39 56 55 48 48 14 47 50 58 12 61 41 66 21 62 64 57 32 54 30 30 50 45 40 56 38 38 43 76 44 84 49 59 84 66 45 57 60 47 42 33 54 74 37 59 26 18 101 80 67...

output:


result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #79:

score: 0
Time Limit Exceeded

input:

100000
1 1 3 4 5 6 7 8 9 10 9 12 13 14 15 14 12 8 19 20 21 20 19 24 24 26 26 28 29 26 31 26 33 34 26 36 36 38 39 40 41 36 4 44 45 46 47 47 49 44 51 52 53 54 53 52 57 58 59 60 61 61 63 61 65 66 67 67 69 70 69 72 59 74 74 76 76 78 79 78 81 82 83 84 85 82 87 87 58 90 91 92 93 91 95 51 97 98 99 99 101 1...

output:


result: