input:

5
716816476 646500411 807499637 544792531 128057616 

output:

result:

input:

7
0 0 1 0 0 0 0 

output:

3 100009
-1 -1

result:

wrong answer Invalid interval.

input:

7
685386610 762888212 32009424 450956771 498508039 313999604 331164353 

output:

result:

input:

10
1 1 0 0 0 0 0 1 1 1 

output:

2 7
-1 -1

result:

wrong answer Not sorted.

input:

10
552474873 603523889 451688250 856980678 746716186 316583031 509750159 895158422 895128023 2769912...

output:

result:

input:

3000
774135042 955379290 425485912 951649655 435211761 517813461 22865164 126834432 859390051 751505...

output:

result:

input:

4000
0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0 1 1 0 0 1 1...

output:

2 4
5 12
13 14
16 18
19 22
23 25
27 28
29 32
34 39
41 42
44 46
50 52
55 56
57 58
59 60
65 67
69 70
7...

result:

wrong answer Invalid interval.

input:

4000
253876655 192406499 33773493 714588720 62247300 512617285 830025704 158991275 146203174 6211898...

output:

1 3
4 6
7 27
8 10
11 26
13 17
14 16
18 25
19 20
21 24
28 42
30 31
32 35
33 34
36 41
38 40
43 70
45 5...

result:

input:

5000
0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 1 0 1 1...

output:

2 7
9 13
14 17
21 22
24 25
28 30
32 34
35 38
40 41
45 46
48 50
51 52
54 61
63 67
68 69
70 71
73 74
7...

result:

wrong answer Invalid interval.

input:

5000
576963277 817862335 430151834 505200145 307373684 896252967 779450344 424741325 188693368 71249...

output:

2 5
3 4
6 18
8 9
10 16
12 15
19 36
20 21
23 35
24 26
27 29
30 33
31 32
37 38
39 53
42 43
44 50
45 49...

result:

input:

5000
296887 701139 1259018 1624742 1747738 2354948 2616510 2777173 3193517 3454408 3801911 4078104 4...

output:

result:

input:

10000
1 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 1 0 1 1 ...

output:

2 3
4 5
6 10
11 22
23 24
25 27
30 31
32 33
35 36
38 39
40 43
44 45
48 51
52 53
57 58
59 60
63 65
67 ...

result:

wrong answer Not sorted.

input:

20000
0 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 ...

output:

3 4
8 9
12 13
16 17
18 19
20 21
24 29
30 31
35 39
42 43
45 48
52 54
55 58
59 61
62 66
67 68
69 70
71...

result:

wrong answer Invalid interval.

input:

30000
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 0 1 1 1 ...

output:

1 3
4 5
7 9
11 12
13 18
19 21
24 26
28 29
31 32
34 35
36 37
39 40
41 42
43 44
47 48
52 54
55 56
57 5...

result:

wrong answer Invalid interval.

input:

40000
0 1 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 ...

output:

2 5
6 7
10 14
15 17
20 23
24 25
29 30
32 35
36 37
39 42
43 45
49 50
52 66
67 68
70 74
76 79
81 83
86...

result:

wrong answer Invalid interval.

input:

50000
0 1 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 0 1 0 ...

output:

2 3
4 5
8 10
12 13
17 18
21 22
28 29
30 32
34 35
37 39
41 42
43 45
46 49
50 53
55 56
57 58
59 62
63 ...

result:

wrong answer Not sorted.

input:

30000
23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 2333...

output:

10001 10005
10002 10003
10007 10011
10008 10010
10012 10047
10013 10014
10015 10016
10017 10046
1001...

result:

input:

40000
45713484 162270600 502896796 450460958 129500884 513441781 557737624 340152311 679444775 35445...

output:

3 5
7 8
9 12
10 11
13 14
15 972
17 23
18 22
20 21
24 33
26 28
29 32
30 31
34 170
35 41
38 39
42 90
4...

result:

input:

50000
455891075 705915927 189674482 578895411 789714247 658466934 483470291 469989305 544838975 2828...

output:

2 4
5 10
6 8
11 85
12 22
13 15
16 21
19 20
23 53
26 27
28 31
32 52
34 35
36 42
37 38
39 41
43 51
44 ...

result: