QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#403415#8127. Slučajna Cestalfxxx#110 ✓1965ms152220kbC++142.0kb2024-05-02 11:09:442024-05-02 11:09:45

Judging History

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

  • [2024-05-02 11:09:45]
  • 评测
  • 测评结果:110
  • 用时:1965ms
  • 内存:152220kb
  • [2024-05-02 11:09:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
bool be;
constexpr int N = 1e6 + 5, mod = 1e9 + 7;
vector<int>e[N];
int n, a[N], dp[N], tp[N], ans[N];
inline int qpow(int b, int k)
{
	int res = 1;
	while (k) {
		if (k & 1) res = (ll) res * b % mod;
		b = (ll) b * b % mod;
		k >>= 1;
	}
	return res;
}
void dfs1(int u, int f)
{
	int c = e[u].size() - (u != f);
	dp[u] = a[u];
	for (int v : e[u]) {
		if (v != f) {
			dfs1(v, u);
			dp[u] = (dp[u] + (ll) (tp[c] - 1) * qpow((ll) tp[c] * c % mod, mod - 2) % mod * dp[v]) % mod;
		}
	}
}
void hg(int u, int v)
{
	int c = e[u].size();
	dp[u] = (dp[u] - a[u]) % mod;
	dp[u] = (dp[u] - (ll) (tp[c] - 1) * qpow((ll) tp[c] * c % mod, mod - 2) % mod * dp[v]) % mod;
	dp[u] = (ll) dp[u] * 2 % mod * (tp[c - 1] - 1) % mod * c % mod * qpow((ll) (tp[c] - 1) * (c - 1) % mod, mod - 2) % mod;
	dp[u] = (dp[u] + a[u]) % mod;
	c = e[v].size();
	dp[v] = (dp[v] - a[v]) % mod;
	dp[v] = (ll) dp[v] * (tp[c] - 1) % mod * (c - 1) % mod * qpow(2ll * (tp[c - 1] - 1) % mod * c % mod, mod - 2) % mod;
	dp[v] = (dp[v] + (ll) (tp[c] - 1) * qpow((ll) tp[c] * c % mod, mod - 2) % mod * dp[u]) % mod;
	dp[v] = (dp[v] + a[v]) % mod;
}
void dfs2(int u, int f)
{
	ans[u] = (dp[u] + mod) % mod;
	for (int v : e[u]) {
		if (v != f) {
			hg(u, v);
			dfs2(v, u);
			hg(v, u);
		}
	}
}
bool en;
int main()
{
	cerr << (&be - &en) / 1024.0 / 1024 << " MB\n--------------------------------" << endl;
#ifdef IAKIOI
	freopen("in.in", "r", stdin);
//	freopen("out.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 2; i <= n; ++i) {
		int f;
		cin >> f;
		e[f].emplace_back(i);
		e[i].emplace_back(f);
	}
	for (int i = 1; i <= n; ++i) cin >> a[i];
	tp[0] = 1;
	for (int i = 1; i <= n; ++i) {
		tp[i] = tp[i - 1] * 2ll % mod;
	}
	dfs1(1, 1);
	dfs2(1, 1);
	for (int i = 1; i <= n; ++i) cout << ans[i] << '\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: 10ms
memory: 28168kb

input:

2
1
307903 536004

output:

575905
500689959

result:

ok all correct

Test #2:

score: 10
Accepted
time: 3ms
memory: 27944kb

input:

3
1 2
992649 690492 637324

output:

1497226
876301738
251230734

result:

ok all correct

Test #3:

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

input:

4
1 2 3
826918 524416 30987 233038

output:

501126006
889825
375470082
250483002

result:

ok all correct

Test #4:

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

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: 3ms
memory: 28652kb

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: 28548kb

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: 2ms
memory: 27284kb

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: 4ms
memory: 27936kb

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: 0ms
memory: 27280kb

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: 4ms
memory: 27372kb

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: 0ms
memory: 27488kb

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: 3ms
memory: 27908kb

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: 4ms
memory: 28444kb

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: 28204kb

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: 4ms
memory: 28540kb

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: 28088kb

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: 4ms
memory: 28288kb

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: 4ms
memory: 28416kb

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: 3ms
memory: 27564kb

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: 3ms
memory: 28288kb

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: 28712kb

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: 3ms
memory: 27680kb

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: 3ms
memory: 28528kb

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: 4ms
memory: 29024kb

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: 3ms
memory: 29072kb

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: 0ms
memory: 28452kb

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: 0ms
memory: 29148kb

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: 9ms
memory: 28128kb

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: 6ms
memory: 27816kb

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: 0ms
memory: 28412kb

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: 3ms
memory: 27780kb

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: 3ms
memory: 28388kb

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: 3ms
memory: 27448kb

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: 7ms
memory: 28144kb

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: 7ms
memory: 29084kb

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: 11ms
memory: 28468kb

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: 10ms
memory: 28672kb

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: 9ms
memory: 27960kb

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: 5ms
memory: 28668kb

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: 5ms
memory: 27844kb

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: 5ms
memory: 28524kb

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: 3ms
memory: 27432kb

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: 8ms
memory: 29204kb

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: 0ms
memory: 27292kb

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: 0ms
memory: 27868kb

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: 3ms
memory: 28076kb

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: 3ms
memory: 27588kb

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: 3ms
memory: 28980kb

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: 3ms
memory: 28172kb

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: 3ms
memory: 28756kb

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: 3ms
memory: 28472kb

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: 3ms
memory: 29144kb

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: 3ms
memory: 28724kb

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: 30
Accepted

Test #54:

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

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:

117639703
505499720
217392232
736598231
5788082
222979475
58628278
88739356
483103427
892979427
656931297
35461225
221784125
595137445
234234213
853473537
107407778
44940167
361717910
789976791
248194725
446646737
186263945
267774449
772729813
812060700
185754119
449015622
598022002
922192272
822202...

result:

ok all correct

Test #55:

score: 30
Accepted
time: 202ms
memory: 34512kb

input:

120000
1 1 2 3 5 4 5 6 8 10 11 2 9 14 14 9 16 12 6 16 7 17 11 24 7 18 21 3 13 29 23 12 8 20 20 27 22 31 13 19 39 36 18 37 38 24 47 17 4 15 35 39 23 48 50 21 30 34 10 60 57 51 34 63 33 58 27 30 69 46 66 46 61 69 68 31 54 36 57 25 47 80 48 45 85 19 62 88 50 54 22 66 67 89 76 74 80 87 74 75 59 41 32 10...

output:

727304663
355472490
462617883
941694097
689986532
682263666
596099564
338032623
562772851
35982083
590846989
881365594
391629792
317015282
589762863
776424897
909838528
843612804
380282938
313086297
407902883
212259529
801943217
182623029
689219952
353093239
236302099
591906911
962503319
160318152
2...

result:

ok all correct

Test #56:

score: 30
Accepted
time: 316ms
memory: 36528kb

input:

180000
1 1 3 4 2 4 3 7 2 7 5 6 11 5 11 13 8 13 19 8 6 19 9 23 23 21 22 28 29 28 17 22 30 33 20 30 10 27 21 25 9 12 37 41 18 43 26 46 26 45 14 34 10 48 54 12 47 51 29 51 45 59 44 34 48 60 38 64 32 62 55 39 58 49 14 76 68 54 49 32 52 37 56 25 38 84 43 59 83 42 36 33 83 84 90 78 77 79 80 62 68 53 53 31...

output:

125624698
360269195
114163212
992829457
128973868
205567918
398511928
424245128
617616178
338012939
388814477
136437309
974141592
873753113
615303295
276644353
979489222
581900833
113888039
595032785
723652701
756348240
194868716
12907458
314952980
236658151
109587921
487328299
606906709
954726517
3...

result:

ok all correct

Test #57:

score: 30
Accepted
time: 414ms
memory: 40404kb

input:

240000
1 1 3 2 2 3 6 6 9 10 9 4 13 5 5 14 12 10 8 14 4 19 18 18 15 11 23 26 28 28 23 13 29 16 25 22 27 17 30 33 15 33 36 17 24 37 19 21 20 42 48 25 46 43 35 56 20 36 29 54 51 22 38 44 34 16 39 57 59 68 12 30 8 41 71 58 66 39 64 57 71 37 38 68 27 82 62 65 11 43 81 88 40 94 77 26 47 53 70 49 31 31 45 ...

output:

986214575
391879844
313769139
988788582
582063594
716604697
540446330
377443771
401533213
34492372
384982640
454445589
4911223
784449196
389188243
67548065
615696023
151585232
870808843
518761490
976218926
363166900
710605865
623467875
106211884
156736621
953691903
865467745
566135268
481648566
8743...

result:

ok all correct

Test #58:

score: 30
Accepted
time: 523ms
memory: 42204kb

input:

300000
1 2 2 1 4 6 6 7 7 3 5 11 3 12 5 9 13 12 18 17 9 18 8 13 11 4 8 23 26 28 14 21 17 28 21 23 20 26 14 33 35 29 40 36 25 16 36 24 10 44 40 27 20 51 15 41 57 55 32 46 56 60 51 24 33 54 16 45 27 42 46 34 60 31 75 31 15 72 10 57 25 78 59 39 75 34 77 55 74 59 74 53 42 32 91 81 68 81 38 49 61 101 90 5...

output:

750785761
597404924
673403925
751419134
10718579
518101741
555640497
907224986
51818674
590609771
635692320
790839775
212618588
469669457
492495732
174195963
271828353
946990353
669109837
230112420
935060851
833777315
347012220
194524388
420629072
729937293
452119488
441086334
668908114
135599074
90...

result:

ok all correct

Test #59:

score: 30
Accepted
time: 644ms
memory: 44984kb

input:

360000
1 2 3 3 2 5 7 4 8 9 11 7 11 4 5 1 8 17 12 20 21 14 14 12 19 23 27 10 28 21 30 16 23 10 35 19 25 25 39 32 26 40 24 34 44 39 9 22 36 40 31 41 37 42 55 56 32 55 42 54 45 41 16 52 52 37 33 56 65 44 54 17 48 30 18 36 70 43 61 38 26 20 6 72 22 76 35 83 89 49 80 81 65 70 79 31 89 13 67 61 81 80 103 ...

output:

386620302
980588341
347083394
562055862
711003035
91247448
375101956
618309877
238529758
636332258
821602603
419200136
89387071
856004473
597904191
719995083
636809473
656249909
23537711
645094972
449693725
609160582
628867140
181682789
493333037
393960661
295482619
474705141
979224777
245171838
226...

result:

ok all correct

Test #60:

score: 30
Accepted
time: 774ms
memory: 48544kb

input:

420000
1 1 2 2 5 4 4 5 9 6 3 8 11 9 8 7 13 6 12 19 7 19 22 20 14 11 16 20 3 24 29 14 21 23 12 16 13 30 23 21 37 24 35 38 18 40 32 35 26 10 17 34 25 47 53 53 31 26 50 31 48 45 28 40 49 15 38 65 44 63 63 72 37 60 18 62 45 48 22 57 66 39 33 46 73 56 74 85 61 80 36 51 78 75 46 39 10 32 75 55 87 77 42 44...

output:

891229885
715977939
775201734
92135714
117564002
662375025
78928908
783087500
425484239
891160431
337979819
524470979
178370469
39507541
790150020
265761028
408037199
815328686
305467051
634848592
829682279
934008008
704167771
354224802
556946345
677986837
994973169
466546761
101491208
107153811
522...

result:

ok all correct

Test #61:

score: 30
Accepted
time: 902ms
memory: 51804kb

input:

480000
1 2 2 3 5 4 3 6 9 8 10 11 10 7 14 14 8 13 6 15 9 17 11 13 5 12 1 19 7 21 22 22 4 33 20 35 31 18 38 40 26 32 30 44 12 34 16 16 37 24 32 21 51 50 43 29 41 42 20 18 35 30 48 41 15 50 19 24 33 64 59 53 47 51 42 72 39 49 44 48 27 66 77 74 59 85 53 81 85 67 26 86 68 65 74 40 77 66 47 87 45 23 76 86...

output:

838857188
211732915
728920916
6097501
938782381
536183407
998705590
865721770
42475800
444960229
697676495
519727799
90131383
956160093
686096369
142976790
401525146
31252886
558447952
626521606
847493338
635781162
221312136
954915783
453882044
705789487
691995058
446131558
862250891
775810264
60812...

result:

ok all correct

Test #62:

score: 30
Accepted
time: 1025ms
memory: 53760kb

input:

540000
1 2 3 3 4 6 6 8 4 10 9 9 2 11 11 7 8 15 12 10 19 16 16 23 15 14 5 17 23 26 7 12 20 30 30 22 25 28 35 40 17 20 18 42 13 40 19 21 24 28 41 50 24 5 14 55 33 58 54 55 18 22 29 50 64 52 35 37 29 65 58 43 59 51 36 53 31 49 33 44 49 63 80 54 25 32 76 48 87 66 83 92 89 91 36 87 59 84 80 34 57 60 82 7...

output:

218337709
753563758
104923237
853597343
610199775
527932517
423050899
872943619
844067878
157157109
265064222
9640148
180803610
560389679
29311807
689638170
210729350
929830888
812526249
433617466
584961517
327285862
528366577
367213417
884056647
674119278
642036710
158605346
620455729
799670799
561...

result:

ok all correct

Test #63:

score: 30
Accepted
time: 1136ms
memory: 56552kb

input:

600000
1 2 3 4 3 5 5 4 2 8 1 7 10 8 11 13 11 18 10 7 13 18 15 6 17 20 26 19 29 12 23 31 14 30 35 12 27 24 29 15 28 16 16 37 41 36 25 19 46 33 41 32 45 27 54 46 17 48 34 59 36 34 57 48 58 53 65 32 44 62 6 54 59 49 50 63 40 58 43 51 55 66 49 84 76 51 65 87 9 22 86 14 31 37 89 95 66 79 40 79 44 42 47 7...

output:

196442068
94265043
21185905
996554435
331677968
841401316
315757248
583719505
843795594
274428568
226525614
611186096
479764490
614142723
753645904
102164865
35884426
988725491
795832988
89602098
391893811
619300934
521896498
794855348
135080045
384168994
512148256
756525131
768995985
678776163
4456...

result:

ok all correct

Test #64:

score: 30
Accepted
time: 1222ms
memory: 59388kb

input:

660000
1 2 3 2 1 6 3 7 8 9 4 8 9 13 13 5 5 7 17 10 20 18 15 23 17 11 19 18 28 30 29 6 21 15 19 27 34 12 16 16 31 35 23 44 36 44 22 14 31 42 48 24 53 37 12 14 55 30 48 35 59 22 36 42 59 45 11 39 21 66 34 56 55 66 27 46 20 32 71 73 81 25 26 37 80 10 87 68 47 67 41 60 84 67 77 57 47 83 28 29 46 68 97 3...

output:

82497201
204545685
213359758
399221318
648402308
635979772
673147729
706839903
173507611
477877493
459286700
489835447
667589662
279609800
580658090
755183011
796467253
158535731
114750187
797576932
581185214
143687729
851002555
296518048
549851243
497717843
796647313
939179788
720862026
496958971
3...

result:

ok all correct

Test #65:

score: 30
Accepted
time: 1342ms
memory: 62076kb

input:

720000
1 2 1 4 2 5 6 5 9 9 11 12 12 7 10 6 7 14 17 13 20 3 22 11 20 17 3 4 15 8 8 26 25 27 14 24 13 31 10 40 21 34 37 16 35 26 38 37 21 15 31 25 23 27 45 19 56 52 24 23 43 36 22 49 35 41 32 52 61 56 47 50 42 72 69 69 63 48 33 79 42 39 50 53 44 68 63 87 88 88 49 38 58 43 18 62 55 75 39 84 55 71 84 96...

output:

87265428
865359809
148327093
136140816
484258955
60120768
556012702
104049494
364602462
792792536
911720400
189345432
471503359
94775099
89140870
109517796
137483052
450767960
780387000
657040118
696995820
575082934
96175124
621335972
629753557
531040277
487337146
559273507
843172395
908341509
91271...

result:

ok all correct

Test #66:

score: 30
Accepted
time: 1458ms
memory: 64252kb

input:

780000
1 2 1 4 4 3 2 8 7 10 9 12 7 6 10 5 3 6 8 12 14 5 18 21 16 17 15 17 20 26 29 31 9 20 15 31 34 23 34 26 13 35 27 11 30 30 27 18 46 42 32 22 23 24 37 35 38 24 22 58 42 44 19 47 49 13 37 46 11 55 64 48 51 60 40 54 75 78 58 63 64 41 66 76 77 65 63 54 49 69 60 77 62 72 59 83 68 98 76 50 57 16 87 41...

output:

234259462
427967239
24858221
685220800
820878610
909754379
561396953
240758520
900192838
429911668
995174805
94473548
569600040
324108297
533519341
521264412
774513909
622957365
223075028
883126656
728215019
603621688
802976417
747241693
863479524
490630917
338986110
574403379
875394705
26650146
335...

result:

ok all correct

Test #67:

score: 30
Accepted
time: 1594ms
memory: 66720kb

input:

840000
1 1 3 3 2 4 5 6 6 5 8 2 12 10 4 7 16 7 14 16 17 9 23 8 15 24 15 12 11 30 27 29 25 23 19 9 21 34 14 10 27 41 32 31 45 19 17 20 24 20 26 48 21 51 26 44 57 36 41 46 30 31 50 33 35 18 18 55 53 42 69 33 60 46 58 61 57 51 68 34 13 22 58 52 39 75 32 84 53 61 64 67 85 54 22 63 89 98 54 40 25 40 60 72...

output:

987197784
342456680
319823997
431926075
866411343
443551775
373086547
220232702
237671602
863991970
197952355
177132547
637579006
475284219
30633113
907318739
417012204
210861099
396733928
501544963
539961237
534945009
695353381
899608709
943147778
736515614
291604809
892740753
631496892
358900890
4...

result:

ok all correct

Test #68:

score: 30
Accepted
time: 1885ms
memory: 74156kb

input:

1000000
1 2 1 3 5 6 2 6 9 7 4 5 4 13 7 8 14 10 9 13 3 22 10 8 25 14 19 20 27 16 18 28 15 20 23 32 26 19 28 11 35 37 24 25 11 35 37 23 46 31 51 45 48 12 47 16 24 36 49 40 60 12 38 22 47 63 62 27 66 60 43 65 62 33 75 41 64 68 29 69 18 30 75 63 85 40 56 86 59 77 51 72 91 31 77 56 38 61 50 99 57 80 55 5...

output:

989758826
392422866
207860708
905829009
642358070
424613204
728743757
313003726
190170136
595367701
117581599
589819381
992585502
290877247
955744494
98657684
27097502
522025243
116146660
850174377
263392388
270426742
473854645
463113359
900032196
645557621
564993634
86610697
302318274
218742784
625...

result:

ok all correct

Test #69:

score: 30
Accepted
time: 1908ms
memory: 74092kb

input:

1000000
1 2 1 2 3 6 4 5 3 9 6 12 12 11 10 16 16 4 19 10 5 8 21 13 11 19 18 14 21 8 17 20 29 17 24 34 27 15 28 18 7 41 24 39 45 14 23 26 37 23 13 7 44 30 46 40 37 35 40 47 44 56 34 22 26 48 29 50 22 31 61 60 63 36 38 41 77 78 67 53 51 58 72 27 66 85 31 69 52 76 86 88 9 72 89 91 39 32 96 69 99 60 67 8...

output:

939691576
270087967
398551701
460750962
320278285
122589796
422807899
50902446
879588248
703642426
529777004
320137444
853273231
476849438
731759413
700413620
609060292
107515742
617554628
526359280
901927256
527856879
435355989
819965641
308106130
72818288
886447397
704167120
314358236
764502424
24...

result:

ok all correct

Test #70:

score: 30
Accepted
time: 1916ms
memory: 74092kb

input:

1000000
1 2 1 2 5 4 4 6 9 3 6 11 12 7 10 11 16 7 16 8 12 14 17 10 24 14 15 17 5 15 25 30 27 33 29 18 24 37 20 20 25 35 39 13 44 18 38 48 42 8 40 41 41 22 26 33 37 53 57 28 38 9 13 52 63 58 45 58 43 56 39 53 66 35 29 60 26 64 56 19 3 72 75 51 34 49 75 72 81 46 70 77 50 85 83 92 50 78 48 57 81 31 87 5...

output:

383876223
87291142
697610990
893654648
99298212
482017003
266553532
875966899
354573256
124295901
307087273
122001136
654284825
693472283
109217790
613732967
488047846
792183331
740795465
429164181
596655572
59192527
223841642
72951800
635181431
955643289
495630080
709217422
132967405
407166123
1318...

result:

ok all correct

Test #71:

score: 30
Accepted
time: 1879ms
memory: 74100kb

input:

1000000
1 1 3 2 3 2 4 7 5 10 10 6 4 11 5 8 17 17 9 18 12 16 21 24 9 8 22 19 14 11 27 24 26 31 20 31 15 38 32 36 32 14 39 35 42 40 12 44 41 36 6 43 40 27 35 45 15 57 16 29 52 37 46 28 23 56 50 67 49 7 21 71 44 70 58 29 58 37 19 42 66 50 20 18 54 86 84 45 22 64 23 43 82 79 13 77 97 46 64 100 55 55 13 ...

output:

582349369
473327294
459477094
449187099
4208838
454373588
721173656
795320261
757619240
334800448
756311332
563915859
360044024
279601093
15619971
745802699
104339322
467854613
981160979
190213874
712716512
809869630
381167195
170529655
487888563
551633941
522725924
378411543
686011249
944643034
426...

result:

ok all correct

Test #72:

score: 30
Accepted
time: 1910ms
memory: 74044kb

input:

1000000
1 1 2 2 5 6 3 4 9 9 7 12 10 7 12 5 16 18 17 11 6 8 17 24 10 26 3 21 28 29 23 28 4 16 13 31 27 29 24 11 27 19 21 33 40 46 26 13 23 31 35 44 37 52 34 54 33 46 42 30 51 48 57 52 34 35 20 43 45 14 20 53 72 53 40 30 15 41 56 66 8 57 14 38 84 80 41 78 58 75 69 90 58 36 93 61 78 81 45 87 95 80 49 2...

output:

553157904
602750160
249802084
989864943
51260138
270291998
500415106
152375685
393408657
495532630
343990114
365426907
132914255
415012218
975083327
518052793
995661124
587172808
78983230
984900044
280725837
926841842
629092240
780599718
214472739
174846700
673411652
356694849
830892678
745465027
83...

result:

ok all correct

Test #73:

score: 30
Accepted
time: 1961ms
memory: 74164kb

input:

1000000
1 1 3 2 4 4 7 5 5 9 2 7 3 9 15 14 16 8 17 19 21 20 10 20 8 16 21 22 26 28 18 19 11 32 30 34 24 35 26 35 32 39 38 38 25 15 14 46 17 41 46 23 34 48 11 49 54 30 39 44 27 55 12 36 18 24 61 57 45 62 23 59 47 48 69 50 12 70 36 71 73 57 72 80 50 53 52 78 77 27 59 85 66 53 80 76 51 42 85 13 22 29 45...

output:

930837522
874242280
779159954
230178465
358135420
435108819
126453091
971820094
899871140
170780424
410941701
88218777
520324844
753276415
861284468
297523687
515131203
339155469
963228706
502887458
647308287
819505193
945024153
590218863
283859745
742878093
135034305
831378737
861880079
475845937
9...

result:

ok all correct

Test #74:

score: 30
Accepted
time: 1910ms
memory: 74108kb

input:

1000000
1 2 2 1 5 4 6 7 9 8 10 10 6 14 4 5 12 16 15 19 14 7 18 20 18 13 22 11 28 22 27 26 21 33 25 29 13 19 17 38 35 29 36 24 35 42 44 36 11 41 42 23 34 40 55 39 41 3 40 15 24 60 31 51 12 38 51 52 39 27 58 47 53 53 74 31 58 73 60 68 25 43 63 66 55 37 76 65 70 80 61 75 87 61 73 90 77 83 16 32 47 102 ...

output:

700645453
307681413
389410778
807546743
908262184
631463146
413517827
378315557
159211696
429522633
466475068
410844207
286852143
688471134
138236704
495031002
209202855
356519399
163297609
974027138
746606004
651220283
403777282
243834590
494626207
63193487
872446106
705367194
634393016
987924424
3...

result:

ok all correct

Test #75:

score: 30
Accepted
time: 1908ms
memory: 74192kb

input:

1000000
1 2 2 4 1 6 6 7 3 7 3 12 4 13 5 5 15 15 18 19 18 16 21 20 8 26 23 25 25 10 22 22 27 11 19 8 10 26 29 37 32 16 33 29 21 36 32 20 30 27 45 37 24 52 23 50 38 39 33 52 55 60 31 40 61 47 38 44 14 61 48 54 43 72 70 41 73 12 79 69 49 17 13 30 51 77 17 11 58 80 91 69 35 34 71 34 54 83 74 75 62 57 67...

output:

170652372
437372204
877740954
306078560
168986759
417729276
829887323
211863573
726341898
306127020
288648294
351545406
735172866
35277771
289965197
690220310
566286466
118499866
38982936
496853144
642247065
978868341
338192866
454306969
729583333
127852713
916119868
272173867
338857258
169632874
19...

result:

ok all correct

Test #76:

score: 30
Accepted
time: 1940ms
memory: 74100kb

input:

1000000
1 2 3 3 2 4 6 7 7 8 6 1 13 5 9 11 8 11 16 15 9 19 21 19 14 21 16 12 17 22 30 32 15 22 33 14 13 20 26 18 10 42 36 34 4 27 27 29 26 45 50 50 25 46 53 24 24 41 54 10 20 18 33 44 23 36 5 63 32 65 70 39 52 45 57 58 58 41 75 51 47 67 57 31 25 29 38 81 71 61 53 65 55 61 17 70 73 77 71 94 87 62 64 8...

output:

743666168
187563892
611344118
215149766
198953410
200503702
405692720
684390242
340940837
93509131
715932581
659131190
383524706
628193586
393175754
244347980
131376137
226995034
963112455
488742395
834774230
430512463
908921446
837945594
679472220
349245334
815440200
699624112
249011494
523541709
8...

result:

ok all correct

Test #77:

score: 30
Accepted
time: 1920ms
memory: 74112kb

input:

1000000
1 1 2 3 3 2 6 5 8 4 9 9 5 13 8 14 6 16 13 16 10 21 17 24 23 25 24 20 20 4 17 31 23 31 26 29 22 27 10 39 18 11 34 26 33 35 32 46 7 12 21 22 39 25 38 18 32 42 44 46 7 48 15 63 62 12 59 57 49 43 52 14 53 37 72 57 49 66 43 55 67 51 41 44 80 55 37 61 88 70 52 89 40 40 80 73 63 75 67 75 65 93 77 7...

output:

5682824
500178271
930219512
325777491
526252587
364660630
715796977
661664179
825446483
353517059
587872133
482106145
145219684
319403134
75195296
985522907
589442488
110682554
19698576
816469516
115710286
144291761
28507260
426911102
130161060
218726919
822424268
987039229
542593635
267191025
41349...

result:

ok all correct

Test #78:

score: 30
Accepted
time: 1447ms
memory: 152104kb

input:

1000000
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 ...

output:

178233829
766686767
281747303
687871177
936825299
404213876
322782339
652280006
307711708
367017646
359596735
531355648
717716814
13180532
313800835
20037394
735551888
568161516
684894649
644080970
924759754
667412845
993082727
814742884
292619948
415884347
496353547
824973183
65461822
837644555
278...

result:

ok all correct

Subtask #4:

score: 40
Accepted

Test #79:

score: 40
Accepted
time: 153ms
memory: 33236kb

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:

736079324
657978221
595430141
440220745
849109682
291128321
127967213
916169355
473854641
262093747
675127246
942295678
513318668
117018684
40656034
777510525
834413159
623705754
678773095
899648692
551558006
117893600
891440155
904413463
37014957
664482432
944982499
639073421
725783142
900552661
26...

result:

ok all correct

Test #80:

score: 40
Accepted
time: 303ms
memory: 37204kb

input:

200000
1 2 2 2 5 6 1 8 9 10 11 11 13 13 13 11 17 18 18 20 21 20 23 23 10 26 26 28 28 10 31 31 33 31 35 35 37 38 38 31 41 42 43 31 45 45 47 47 49 50 49 45 53 54 55 54 57 58 59 60 60 62 63 64 65 66 67 64 69 70 71 72 73 57 75 76 77 78 78 80 80 82 83 84 85 86 87 88 89 90 89 89 93 94 80 96 77 98 99 100 9...

output:

633762052
575094185
258491155
945293942
706047256
697532938
48421895
150719727
492381221
593896564
187164727
505953927
505518359
131263428
881670389
402304166
714177765
643084683
315260723
175027917
38945357
942642408
978740055
888369511
326223454
659816926
540856638
341648647
398498144
398257527
49...

result:

ok all correct

Test #81:

score: 40
Accepted
time: 440ms
memory: 42272kb

input:

300000
1 2 2 4 5 5 7 8 9 10 11 12 13 7 15 15 17 17 19 19 19 22 23 24 22 26 27 26 29 26 31 32 33 34 33 36 37 38 37 40 41 42 43 42 45 45 45 45 49 45 45 52 53 54 55 56 54 58 58 60 61 62 53 64 64 66 64 15 69 69 71 72 73 73 75 75 77 78 78 71 81 82 82 81 81 86 87 88 89 88 91 91 93 94 93 96 96 93 99 100 10...

output:

61361787
855330322
394986496
334772249
523174961
828091277
488176364
680972282
469650737
743322291
888388665
726299691
426076156
451350070
43683017
994007451
65934423
96368056
793456929
101394174
372071529
301585188
102218069
82819164
805356625
210787828
702834988
551753941
288587017
526152974
48450...

result:

ok all correct

Test #82:

score: 40
Accepted
time: 591ms
memory: 47948kb

input:

400000
1 2 3 4 5 4 7 8 8 10 8 12 12 14 15 16 14 18 19 18 21 22 22 24 25 26 25 25 29 25 31 31 33 33 35 25 37 37 39 40 41 42 43 44 45 46 45 45 49 50 50 52 50 54 55 55 54 54 59 60 60 62 63 54 65 65 45 68 68 70 68 72 73 72 75 75 77 78 44 80 81 82 82 84 85 81 87 88 89 89 91 92 89 94 94 96 81 98 42 41 101...

output:

365629677
172755531
406985385
167803383
223204200
65659876
318541786
130307812
427127333
289298887
692963419
695425250
141337746
376119690
780352520
828027239
385439744
922864230
910633617
357253797
82371736
503443643
226516905
764998618
782737157
524275355
849683125
260413818
893536389
929164312
96...

result:

ok all correct

Test #83:

score: 40
Accepted
time: 728ms
memory: 51192kb

input:

500000
1 2 3 4 4 3 7 8 9 7 11 12 12 14 14 16 1 18 19 20 21 20 20 24 24 26 27 27 29 29 27 32 32 34 35 32 37 38 38 38 41 42 38 44 45 46 47 48 49 50 49 52 53 54 55 52 45 58 59 60 60 62 58 64 65 66 58 58 69 70 71 72 73 73 73 76 77 76 79 79 81 82 69 84 85 85 84 88 88 90 90 92 92 94 90 96 96 98 99 100 100...

output:

791364781
94437580
118444997
110500231
714406406
776759829
706262007
582597583
42080028
695268275
36026652
602998245
780836055
518157031
226179897
935270886
457392694
383747944
954285002
324994400
460940962
641178915
280013489
296286492
735598717
246597603
45591001
716061774
599224347
135739243
6982...

result:

ok all correct

Test #84:

score: 40
Accepted
time: 887ms
memory: 56392kb

input:

600000
1 1 3 4 4 6 1 8 9 10 11 11 13 14 15 16 16 18 19 19 21 21 23 23 25 26 27 28 29 30 26 32 33 34 33 33 37 38 39 40 40 42 40 44 25 46 47 48 49 49 51 52 53 54 55 46 57 58 57 60 61 62 63 64 64 64 67 68 68 68 71 64 73 74 14 76 77 78 78 77 81 82 83 84 82 81 87 88 89 90 89 81 81 94 95 95 97 98 98 100 1...

output:

397023423
76817810
337288418
339525627
40144093
975411774
567210817
401586845
700384169
99503495
740766495
315732113
211190911
166896531
189715040
559018359
11401224
955834821
683088890
877306740
486111744
848309891
828262660
764748561
21719676
342808508
198647998
193282434
534702344
893224758
92921...

result:

ok all correct

Test #85:

score: 40
Accepted
time: 1037ms
memory: 61524kb

input:

700000
1 2 3 3 2 6 7 8 9 9 11 12 13 14 6 16 17 17 17 20 21 6 23 24 25 26 23 28 29 30 30 32 32 34 34 36 34 34 30 40 41 42 43 44 44 40 47 48 49 48 47 52 52 54 55 55 55 58 58 52 61 62 63 64 65 65 64 68 2 70 70 72 73 72 75 76 70 78 79 80 81 81 83 84 85 86 86 88 88 90 90 85 93 93 93 96 97 97 99 99 101 10...

output:

165411309
42612857
680522065
125177050
750317703
112787771
209758003
666249941
355440230
157800408
454568812
290656779
20800059
11031621
340968390
754579666
957835470
589850802
527164946
563937659
876158434
501313029
239953718
3083373
267379571
665617666
527148462
430773625
271618002
802946273
34855...

result:

ok all correct

Test #86:

score: 40
Accepted
time: 1175ms
memory: 65800kb

input:

800000
1 2 3 4 5 6 7 7 9 6 11 12 11 11 15 15 11 18 18 18 21 22 23 24 11 26 26 26 29 30 30 32 33 34 33 36 37 38 39 32 41 41 43 44 32 46 47 48 49 49 51 48 53 53 55 56 57 58 56 55 61 61 61 61 55 66 67 68 69 67 66 72 73 74 75 76 74 74 79 80 81 82 80 84 85 86 86 88 86 86 91 85 93 93 95 96 79 98 99 100 10...

output:

474439688
960837343
46362081
134321948
135245828
392468530
830151078
257618084
537171299
191860298
661404091
177671282
952407708
71188745
111765880
518698997
456268081
684535717
114175266
364135262
371032370
842551443
233897093
242507536
495235641
565656305
289903352
352229638
354182327
389874523
29...

result:

ok all correct

Test #87:

score: 40
Accepted
time: 1317ms
memory: 70236kb

input:

900000
1 1 1 4 5 6 7 4 9 10 11 10 13 14 10 16 17 18 19 20 21 22 23 22 25 25 27 21 29 30 31 31 31 34 34 31 37 38 39 40 41 38 43 43 43 43 47 48 49 50 51 38 53 53 55 56 37 58 59 60 61 60 60 64 59 66 67 68 66 70 71 70 66 74 75 75 66 78 79 80 80 82 83 66 85 86 85 88 89 18 91 91 93 94 95 96 97 95 93 100 9...

output:

452899196
657376034
32137595
740896437
830125649
352833523
302144729
201737721
671300597
435962960
913710227
109512474
816041478
752491861
418332322
551927008
803454953
118158274
272435458
459432948
209054111
897554998
977147333
568258389
805483859
134324951
280276062
770473217
927582192
255265789
4...

result:

ok all correct

Test #88:

score: 40
Accepted
time: 1446ms
memory: 74460kb

input:

999750
1 2 3 4 2 1 7 8 8 10 10 12 12 12 15 16 16 15 19 19 8 22 22 22 25 25 27 28 28 22 31 32 32 34 34 36 37 36 39 40 34 42 43 44 45 45 47 48 49 50 50 50 53 54 55 56 57 58 59 60 60 59 55 64 65 66 67 67 69 70 70 72 72 72 75 75 70 78 78 80 81 82 81 84 78 86 87 88 89 90 65 65 93 93 95 96 93 98 98 100 10...

output:

750564394
474610110
883793291
817353221
878389531
573273516
392918386
857332269
729638965
83054643
910557206
322320349
5400743
900960991
722442840
456741724
624416770
811657297
180843492
331153475
581071281
974892529
378176531
807467389
466333915
300449569
137032672
555018157
875153994
437710220
940...

result:

ok all correct

Test #89:

score: 40
Accepted
time: 1447ms
memory: 74476kb

input:

999900
1 2 3 4 4 6 6 8 9 4 2 12 13 14 14 14 17 18 18 18 18 18 23 24 25 26 26 28 29 23 31 17 33 34 35 36 37 38 36 40 41 36 43 44 45 45 45 44 49 49 51 12 53 54 55 54 53 58 58 60 58 62 63 64 62 66 62 68 69 70 69 72 73 73 75 76 75 78 78 80 62 82 83 84 85 86 82 88 89 90 90 90 90 94 95 96 97 98 99 100 100...

output:

626990845
371104483
262396353
632580802
144309316
463822582
263078361
337617970
794082246
863091909
560930028
798995782
757093830
317341243
217029001
988186162
542077084
247988777
343636024
718923690
690431919
94152104
998553326
66352800
593813856
813050921
478252281
206964370
947658701
882364542
52...

result:

ok all correct

Test #90:

score: 40
Accepted
time: 1475ms
memory: 74348kb

input:

999900
1 2 3 4 4 6 7 8 7 10 11 11 13 11 15 16 15 18 19 20 20 3 23 24 24 26 27 28 29 30 31 32 31 31 35 29 37 38 38 28 41 42 43 43 45 45 45 48 49 49 51 52 52 54 55 54 24 58 59 60 60 62 63 62 59 58 67 24 69 70 71 71 73 74 75 73 77 78 79 80 79 82 79 84 79 86 69 88 89 89 91 92 93 92 95 96 96 98 96 100 10...

output:

530729158
929901441
167898971
982570651
516251015
654243061
563592701
101773304
318317901
343104966
298827039
136393870
657145923
354773656
347281101
483765085
239567115
800248099
556608647
876985599
796042153
45848737
391488673
66456267
976782862
466062482
262855168
231230684
322781856
12178032
646...

result:

ok all correct

Test #91:

score: 40
Accepted
time: 1476ms
memory: 74452kb

input:

999375
1 2 3 4 3 6 7 7 7 10 6 12 13 14 15 15 17 18 19 20 21 22 18 24 25 26 27 26 29 30 31 32 33 32 35 36 37 38 36 40 41 41 43 40 40 46 47 48 49 50 51 52 52 54 51 56 57 56 59 59 51 62 62 64 65 65 67 67 69 70 70 72 72 72 75 69 62 78 79 80 80 82 83 84 79 86 87 88 89 87 91 87 93 94 93 96 29 98 98 100 10...

output:

516181419
407440044
134365096
280853449
603832195
359062640
780345630
248248314
415028627
529960397
186748761
102542149
104814002
158015747
239401804
698742378
877088972
105702826
453463168
867873069
216136479
921265499
114702790
703963142
69923649
463342503
259265258
506745655
689174512
465798411
9...

result:

ok all correct

Test #92:

score: 40
Accepted
time: 1455ms
memory: 74460kb

input:

999600
1 2 2 2 5 6 7 5 9 5 11 12 13 2 15 16 17 18 18 20 21 21 18 24 25 26 27 28 29 30 25 32 33 34 35 36 35 38 39 40 41 40 43 44 45 46 47 46 43 50 50 50 50 50 55 55 57 57 59 55 61 62 62 62 65 62 67 68 69 68 71 72 72 68 75 76 77 78 79 76 81 81 83 84 85 86 87 87 89 89 81 92 93 94 94 96 97 55 18 100 100...

output:

68051531
321634204
848205824
145117507
77500824
786142335
705862872
637631507
12667083
175782357
623981455
78483488
821263673
297592185
53903752
461362535
848349963
947070087
984449969
474846127
955470012
686299681
873674303
989098602
441894209
280885528
86039508
934420156
498823017
812564269
375369...

result:

ok all correct

Test #93:

score: 40
Accepted
time: 1466ms
memory: 74420kb

input:

999000
1 2 3 2 5 5 7 8 9 5 11 12 13 13 15 12 17 18 19 20 21 22 22 24 24 24 27 28 27 30 31 31 33 31 35 30 37 38 20 40 41 42 43 42 45 46 47 48 47 50 50 52 53 11 55 56 57 58 59 60 61 58 63 63 65 65 63 68 58 70 71 71 73 74 74 73 77 78 77 80 81 82 77 84 85 86 86 86 89 90 71 92 92 94 95 94 92 98 98 100 10...

output:

796252307
560903105
71135782
464003868
100939139
249704347
837879149
123047568
218301751
896124088
139803653
327134684
236752081
259898086
281019045
270700526
960354793
480723699
740452434
793114462
575013068
899504040
989675613
297781005
402194945
339497937
618318113
174639572
866517638
517852942
9...

result:

ok all correct

Test #94:

score: 40
Accepted
time: 1453ms
memory: 74344kb

input:

999600
1 1 3 4 4 6 7 8 9 8 11 12 7 14 15 16 15 18 19 19 21 21 23 24 25 26 27 28 29 28 31 32 33 32 32 36 37 38 38 40 26 42 42 44 45 46 47 48 46 45 3 52 52 54 55 56 57 58 58 60 61 61 56 64 56 66 56 68 69 70 70 70 73 74 74 76 73 73 73 80 81 82 83 83 80 86 87 70 89 90 91 91 93 94 95 96 91 90 99 90 55 10...

output:

64897639
116393647
314641967
560426625
851273829
176481120
984859156
659596600
895318952
13583186
591201586
296143592
531279292
574580074
596051553
571978389
631410391
31723450
323026430
47025851
310982464
128863389
803945507
438199327
540502956
796195296
869221302
130656397
494190868
163013807
3308...

result:

ok all correct

Test #95:

score: 40
Accepted
time: 1465ms
memory: 74396kb

input:

999600
1 1 1 4 5 6 6 8 9 9 11 9 13 13 15 15 17 17 15 20 20 22 23 23 25 26 27 28 29 30 31 32 33 32 35 36 37 37 39 39 39 39 43 44 45 46 37 48 48 48 51 52 52 52 55 56 57 58 59 58 61 57 63 64 65 63 67 68 68 70 71 63 52 74 75 76 75 78 75 80 81 82 83 84 85 86 86 88 89 90 91 90 90 94 94 94 86 85 99 100 101...

output:

663285585
867917671
643181808
836149172
541580722
354927423
496424403
626559185
732100996
380938312
402935869
519223794
772372304
308980029
538098437
17321547
59405283
726183168
350917382
455533983
337709217
752906406
370046617
604696883
209173831
317489409
583059222
281672503
210997442
2401874
4496...

result:

ok all correct

Test #96:

score: 40
Accepted
time: 1448ms
memory: 74372kb

input:

999000
1 2 2 4 5 6 7 8 9 10 11 4 13 14 15 16 17 17 19 16 21 21 21 21 25 26 26 28 29 29 25 14 33 34 34 36 37 37 37 40 41 40 43 44 44 46 47 48 49 50 51 52 50 54 55 56 54 58 59 60 58 62 63 64 65 66 67 64 69 70 50 72 73 72 75 76 77 75 79 80 81 75 47 84 84 86 87 87 89 90 90 92 87 94 95 96 95 98 99 100 98...

output:

434777101
366928675
928475544
340237611
680829370
742332437
924627995
568197325
245315297
295197265
742108788
78083827
718153548
882342558
114788802
28943294
60103043
860523623
614230244
743084427
371339991
88520519
127778323
88350002
22159130
999557687
705288998
963636936
494239857
988108598
175530...

result:

ok all correct

Test #97:

score: 40
Accepted
time: 1454ms
memory: 74376kb

input:

998925
1 2 2 4 5 6 7 2 9 9 9 12 12 14 12 16 12 18 18 20 21 22 23 24 25 26 24 22 29 29 29 20 33 34 34 34 37 34 39 20 41 42 43 44 45 46 47 48 48 50 48 52 53 52 46 56 57 57 57 60 61 62 63 64 41 66 66 68 69 70 71 72 71 71 75 76 77 78 79 78 81 81 83 84 85 84 78 88 89 89 91 92 91 94 68 96 96 98 98 100 96 ...

output:

156032115
324435563
49029066
919462522
15096977
617922131
278477613
436102577
153439741
81859623
436228874
776661671
659365926
658453183
439202443
359083406
156491574
265031446
500938082
340044251
549386061
32510813
351938995
56581523
753804065
283450655
272974849
385162454
300491561
650186326
33759...

result:

ok all correct

Test #98:

score: 40
Accepted
time: 1919ms
memory: 73988kb

input:

1000000
1 1 2 2 3 4 7 6 4 9 6 10 13 11 12 13 16 9 12 18 11 5 21 15 5 10 20 20 3 22 30 17 28 31 19 34 28 19 22 38 39 32 7 34 27 45 21 38 31 16 39 33 42 52 14 14 43 24 42 49 51 46 58 15 8 40 17 46 26 35 51 70 33 65 72 56 26 18 24 78 70 53 25 53 62 57 25 60 56 45 89 67 82 81 30 47 50 92 85 71 43 54 23 ...

output:

82744832
437363790
487097901
724679204
729238003
324986383
160320937
534587195
585453820
377487489
49147918
647844910
532401148
417957651
936492340
666419466
121193847
700998609
583086836
694286950
985185915
257205634
682481701
113295332
458468810
441182251
211028726
1227726
540671020
61602271
78563...

result:

ok all correct

Test #99:

score: 40
Accepted
time: 1919ms
memory: 74136kb

input:

1000000
1 2 3 4 3 1 2 5 9 7 10 10 12 7 13 4 12 6 9 17 6 8 22 11 24 19 8 16 11 5 23 29 33 15 23 28 16 14 27 15 31 14 29 17 26 19 30 47 21 44 30 33 40 28 32 47 55 42 55 13 50 34 31 21 41 63 45 59 43 56 67 56 53 58 40 63 24 22 66 49 45 78 58 53 77 39 71 87 50 49 76 64 77 59 76 72 75 75 71 95 60 87 44 9...

output:

689178861
351318639
551934531
411940412
239529738
246909908
957209317
440581005
469908363
993669951
474882835
429754419
92828802
261938365
333448856
995150426
379494373
905215627
562347055
592913528
749226030
532789103
178298893
263805338
61180075
431385685
694233128
918462483
973533109
644575579
58...

result:

ok all correct

Test #100:

score: 40
Accepted
time: 1939ms
memory: 74100kb

input:

1000000
1 2 3 4 4 6 5 2 1 10 5 7 8 7 13 16 12 13 8 6 16 11 15 23 11 14 23 28 22 18 30 20 20 17 29 19 37 32 30 24 34 31 22 41 27 31 9 46 17 49 14 39 34 36 43 55 45 9 52 40 37 32 25 36 40 50 51 28 54 66 65 46 71 61 3 15 44 50 76 71 62 62 53 27 19 60 57 24 77 47 10 56 64 77 87 85 52 66 70 49 89 92 73 7...

output:

984154490
626174151
441003490
71726679
725145872
591862176
810578115
28864727
539348210
899225860
789041254
584689555
526468668
911350279
970310282
958658754
2535705
15465478
195305131
877290415
306774227
51667966
21894854
598396554
655228899
634205309
474689199
407261774
517619870
967854592
7393818...

result:

ok all correct

Test #101:

score: 40
Accepted
time: 1899ms
memory: 74096kb

input:

1000000
1 1 2 4 3 2 3 4 8 5 9 6 8 7 5 6 7 18 16 19 18 16 10 12 10 14 19 21 25 22 29 23 11 30 33 9 35 14 30 32 13 38 15 26 23 15 38 33 32 41 43 34 24 49 44 47 34 25 58 17 44 26 17 47 51 61 20 68 62 63 39 41 37 74 48 24 35 64 72 77 60 58 71 62 29 66 78 69 27 81 52 59 54 78 90 93 53 85 79 75 88 79 93 8...

output:

834847759
363113268
258045636
468408566
193584194
448811997
777523517
989893812
488394085
880701004
824395697
647865162
394677815
741221455
228127133
657952088
393110213
106835628
249272380
372245498
216451954
46734099
307443653
616354686
495425502
928615752
706994268
609344584
142970997
805647640
4...

result:

ok all correct

Test #102:

score: 40
Accepted
time: 1965ms
memory: 74104kb

input:

1000000
1 1 3 3 2 4 2 7 8 10 9 8 6 5 14 15 16 6 15 19 19 14 16 20 9 24 7 24 25 28 25 28 17 23 22 13 29 27 33 36 37 33 11 27 22 30 38 20 17 40 42 30 37 46 47 32 41 55 57 49 29 32 54 5 41 47 26 53 10 11 42 68 39 13 48 36 58 65 72 50 48 80 69 73 63 77 70 70 88 18 64 69 56 54 91 75 12 94 51 62 100 40 44...

output:

303043886
740975389
801841097
897065924
217409575
922885749
408186116
61446471
29467147
911599305
360857859
810134917
889921423
349728866
848452542
141181626
165937754
385845718
102220253
57422069
282923431
462934957
990938078
843446548
704541806
785094072
335332878
591794741
695992989
108802954
399...

result:

ok all correct

Test #103:

score: 40
Accepted
time: 1460ms
memory: 74660kb

input:

1000000
1 2 2 4 5 5 7 7 9 9 5 12 12 14 14 5 17 18 19 19 21 22 23 24 22 26 27 26 18 30 30 32 33 34 34 34 37 38 39 40 34 42 42 42 45 46 42 48 42 50 50 50 53 53 55 56 57 58 56 60 60 62 63 64 64 66 34 68 69 70 71 72 73 72 75 76 76 78 72 80 81 82 83 72 85 70 30 88 89 90 91 91 90 94 95 96 96 98 99 99 101 ...

output:

972404864
474559666
763688813
812150983
372694635
943951527
939080606
460982870
360012152
883720660
946062331
756776282
424074964
563984902
871828999
58991051
424560471
337178387
29109163
73018817
987963896
376259726
5921610
409864007
689799724
614795428
305872163
537509698
949064569
56589459
349484...

result:

ok all correct

Test #104:

score: 40
Accepted
time: 1453ms
memory: 74568kb

input:

1000000
1 1 1 1 5 5 7 8 9 10 10 7 13 13 13 16 17 18 13 13 21 13 23 23 25 26 27 27 29 30 30 32 33 34 35 36 36 35 39 39 41 42 42 44 44 35 47 48 49 30 51 52 52 51 55 56 51 58 59 59 61 62 63 62 65 65 67 65 69 23 71 72 73 73 75 76 76 76 75 80 80 82 82 84 85 86 23 88 88 90 90 88 93 93 95 96 96 98 99 99 98...

output:

859969691
260666533
593826876
94064406
208358716
142868087
935742065
280716249
269298967
413266967
149650218
462252375
643669472
932878861
374327755
998653012
437110478
344449491
563315182
417442757
452106567
218517218
262709352
707705737
122179635
588958804
694514169
590058327
709341217
917868553
3...

result:

ok all correct

Test #105:

score: 40
Accepted
time: 1446ms
memory: 74632kb

input:

1000000
1 1 3 4 4 6 3 8 9 9 11 12 12 14 14 16 17 16 16 20 20 22 23 24 24 24 27 24 29 30 29 32 29 34 34 36 37 38 37 40 41 41 34 44 45 44 44 48 49 49 51 52 52 51 55 34 57 57 59 60 59 62 63 63 65 12 67 68 67 70 70 72 73 73 75 76 75 75 79 79 79 82 82 84 84 86 86 88 88 90 91 92 93 94 90 96 96 98 88 79 10...

output:

81973425
55247340
259857171
769517527
807468285
51620832
451283707
129264464
783151093
780786252
731308143
827553385
748828969
31008036
903894920
966527335
50076437
950586851
55506273
614508873
600815733
377732901
833838040
769651234
110695099
415765642
699922264
550404816
553210190
729047348
819458...

result:

ok all correct

Test #106:

score: 40
Accepted
time: 1475ms
memory: 74624kb

input:

1000000
1 2 3 4 4 4 7 8 8 10 11 12 11 14 15 16 14 18 19 20 21 22 23 24 25 23 27 28 27 23 31 32 31 34 35 36 37 37 37 40 40 42 43 42 45 45 47 47 49 45 51 52 53 53 55 56 57 58 56 55 55 62 63 64 64 66 66 68 69 62 71 71 71 74 75 75 71 78 79 79 81 82 78 84 85 86 85 88 89 90 90 92 92 94 94 78 37 98 98 100 ...

output:

462497138
568005701
572240079
844983854
277575484
131741351
206546838
631385773
227489782
371793217
867038365
583984676
56602679
742963539
162698189
362910997
991946848
877934178
886481987
837667364
956426029
552824802
225384872
176238155
869590093
663179953
165059858
209367167
473316416
195531146
3...

result:

ok all correct

Test #107:

score: 40
Accepted
time: 1441ms
memory: 74596kb

input:

1000000
1 2 3 3 5 6 7 7 9 10 11 10 13 10 15 10 5 18 19 20 20 20 23 24 25 25 25 28 28 19 31 32 32 34 35 31 37 38 39 40 38 42 43 44 44 46 47 48 47 50 51 52 53 43 55 56 56 58 59 38 61 61 63 64 63 66 67 68 69 69 71 72 72 72 75 69 77 77 68 80 81 81 81 84 85 84 87 84 89 89 91 92 92 94 94 92 97 98 99 100 1...

output:

61731977
217173251
349755799
841219230
895195640
228859258
500684935
241705176
72878093
8758093
684776101
290027618
47263414
948251049
613487579
76046534
321739460
391131284
789160974
720043793
428895604
283314523
768331437
576351878
252120003
488892471
447725155
362395021
715533138
465484097
281141...

result:

ok all correct

Test #108:

score: 40
Accepted
time: 1470ms
memory: 152220kb

input:

1000000
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 ...

output:

739631769
233638222
28380726
87344379
439096950
759504830
959183484
387393590
259071342
508839562
12883042
22463238
792544830
708201373
227376037
359791342
421520773
442986556
935613165
894705556
550519056
730702845
526338288
334512286
808625815
436617394
533154967
645245888
579836332
303903324
6789...

result:

ok all correct

Test #109:

score: 40
Accepted
time: 1409ms
memory: 77468kb

input:

1000000
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 ...

output:

768575905
646995523
953270859
408028456
802271761
659032196
325590291
631165876
708003368
500851449
694014935
178428529
743863890
794156870
485775877
468366855
160031054
739696757
576878760
535913774
336099897
97438791
945289703
263175769
52102839
42373640
366771625
803135436
443925868
526624387
115...

result:

ok all correct

Extra Test:

score: 0
Extra Test Passed