CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)


A. Beautiful Sequence
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
3
3 2 1
4
2 4 3 5
5
2 3 5 5 6
2
3 1
5
2 4 5 2 3
4
5 6 7 8
6
6 5 4 3 2 1
Output
YES
YES
NO
YES
YES
NO
YES
----------------------------------------------------------------------------------------------------
B. Candies
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
2
3
7
17
Output
-1
1
2 
2
2 2 
4
2 1 1 1 
----------------------------------------------------------------------------------------------------
C. Make It Permutation
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
8
3 3 3
1 2 3
5 1 5
1 2 3 5 6
5 2 3
1 1 1 3 3
5 1 10
2 4 6 8 10
6 2 8
7 3 5 4 4 8
4 10 1
1 2 6 7
4 3 3
2 5 8 7
2 1000000000 1
1000000000 1
Output
0
2
8
14
20
3
12
999999998
----------------------------------------------------------------------------------------------------
D. Climbing the Tree
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
3
1 3 2 5
2 4 1
2 3 2
3
1 6 5 1
2 3 1
2 6 2
3
1 4 2 2
1 2 1 3
2 10 2
9
1 7 3 6
1 2 1 8
2 5 1
1 10 9 7
1 8 1 2
1 10 5 8
1 10 7 7
2 7 4
1 9 4 2
9
1 2 1 6
1 8 5 6
1 4 2 7
2 9 1
1 5 1 4
1 5 2 7
1 7 1 9
1 9 1 4
2 10 8
Output
1 2 5
1 -1 1
1 0 1
1 0 -1 0 0 0 1 8 0
1 0 0 1 0 0 0 0 1
----------------------------------------------------------------------------------------------------
E. Monsters
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
4 3
2 1 0 3
1 2
2 3
3 4
6 6
0 1 2 3 0 1
1 2
2 3
3 4
4 5
4 6
5 6
4 3
0 1 2 0
1 2
2 3
1 3
4 6
1 1 1 0
1 2
3 2
4 3
2 4
4 1
1 3
5 5
0 1 3 2 0
1 2
2 3
3 4
4 5
3 5
Output
YES
YES
NO
YES
NO
----------------------------------------------------------------------------------------------------
F. M-tree
time limit per test: 2.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
5 3 3
3 3 4 4 5
1 4
2 4
3 5
5 2 4
3 3 4 4 5
1 4
2 5
3 5
4 5
7 3 4
1 2 2 3 3 3 4
1 4
2 1
5 5
6 6
Output
6 6 6
7 7 7 8
6 6 6 7
----------------------------------------------------------------------------------------------------
G. The Maximum Prefix
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
2
1 2
1 2
1 2 3
3
1 3
1 4
5 5
1 1 1 1
3
2 5
4 6
0 2
4 3 2 1
5
5 6
5 7
1 6
1 3
4 7
9 0 4 5 2 4
Output
500000005 750000007 
1 1 1 
200000005 333333339 333333339 
500000005 880952391 801587311 781746041 789304620 
----------------------------------------------------------------------------------------------------
H. Last Number
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2
4
7
15
177567
Output
1
2
2
4
33914
----------------------------------------------------------------------------------------------------
