Codeforces Round 873 (Div. 1)


A. Counting Orders
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
6
9 6 8 4 5 2
4 1 5 6 3 1
3
4 3 2
3 4 9
1
2
1
3
2 3 4
1 3 3
12
2 3 7 10 23 28 29 50 69 135 420 1000
1 1 2 3 5 8 13 21 34 55 89 144
Output
32
0
1
0
13824
----------------------------------------------------------------------------------------------------
B1. Range Sorting (Easy Version)
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2
6 4
3
3 10 6
4
4 8 7 2
5
9 8 2 4 6
12
2 6 13 3 15 5 10 8 16 9 11 18
Output
1
2
8
16
232
----------------------------------------------------------------------------------------------------
B2. Range Sorting (Hard Version)
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2
6 4
3
3 10 6
4
4 8 7 2
5
9 8 2 4 6
12
2 6 13 3 15 5 10 8 16 9 11 18
Output
1
2
8
16
232
----------------------------------------------------------------------------------------------------
C. Palindrome Partition
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
6
abaaba
1
a
2
aa
6
abcdef
12
accabccbacca
6
abbaaa
Output
3
0
1
0
14
6
----------------------------------------------------------------------------------------------------
D. Two Centroids
time limit per test: 1.5 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
5
2
1
3
1 1
4
1 2 3
7
1 2 3 2 5 2
10
1 2 2 4 5 5 7 8 9
Output
0
0 1
0 1 0
0 1 0 1 2 3
0 1 2 1 0 1 0 1 2
----------------------------------------------------------------------------------------------------
E. Bus Routes
time limit per test: 2.5 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
4
5 2
1 2
2 3
3 4
2 5
1 4
5 2
5 1
1 2
2 3
3 4
2 5
1 5
2 0
1 2
6 3
1 2
2 3
3 4
4 5
5 6
1 3
2 5
4 6
Output
YES
NO
1 3
NO
1 2
NO
1 6
----------------------------------------------------------------------------------------------------
F. Copium Permutation
time limit per test: 2 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
5
5
5 2 1 4 3
4
2 1 4 3
1
1
8
7 5 8 1 4 2 6 3
10
1 4 5 3 7 8 9 2 10 6
Output
15 15 11 10 9 9 
10 8 8 7 7 
1 1 
36 30 25 19 15 13 12 9 9 
55 55 41 35 35 25 22 22 19 17 17 
----------------------------------------------------------------------------------------------------
