Codeforces Round 838 (Div. 2)


A. Divide and Conquer
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
4
1 1 1 1
2
7 4
3
1 2 4
1
15
Output
0
2
1
4
----------------------------------------------------------------------------------------------------
B. Make Array Good
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
4
2 3 5 5
2
4 8
5
3 4 343 5 6
3
31 5 17
Output
4
1 2
1 1
2 2
3 0
0
5
1 3
1 4
2 1
5 4
3 7
3
1 29
2 5
3 3
----------------------------------------------------------------------------------------------------
C. Binary Strings are Fun
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
1
1
1
0
2
11
3
010
9
101101111
37
1011011111011010000011011111111011111
Output
1
1
3
3
21
365
----------------------------------------------------------------------------------------------------
D. GCD Queries
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
2
1
1
5
2
4
1
Output
? 1 2
! 1 2
? 1 2
? 2 3
! 3 3
----------------------------------------------------------------------------------------------------
E. Tree Sum
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
Output
998244352
Input
1
Output
0
Input
4
Output
998244343
Input
10
Output
948359297
Input
43434
Output
86232114
----------------------------------------------------------------------------------------------------
F. Good Pairs
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
3 0
1 1 1
4 2
4 8 6 8
6 4
7 2 5 8 3 8
20 23
110 57 98 14 20 1 60 82 108 37 82 73 8 46 38 35 106 115 58 112
Output
6
9
18
92
----------------------------------------------------------------------------------------------------
G. Unequal Adjacent Elements
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
3
1 2 1
4
1 2 3 4
3
1 1 1
7
1 2 1 1 3 1 4
Output
YES
1 2 3
YES
3 1 4 2
NO
YES
1 2 3 5 4 7 6
----------------------------------------------------------------------------------------------------
