VK Cup 2021 - Final (Engine)


A. Charmed by the Game
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
2 1
1 1
0 5
Output
4
0 1 2 3
2
0 2
2
2 3
----------------------------------------------------------------------------------------------------
B. Up the Strip
time limit per test: 6 seconds
memory limit per test: 128 megabytes
input: standard input
output: standard output

Examples
Input
3 998244353
Output
5
Input
5 998244353
Output
25
Input
42 998244353
Output
793019428
Input
787788 100000007
Output
94810539
----------------------------------------------------------------------------------------------------
C. Bottom-Tier Reversals
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
3
1 2 3
5
3 4 5 2 1
3
2 1 3
Output
4
3 3 3 3
2
3 5
-1
----------------------------------------------------------------------------------------------------
D. Top-Notch Insertions
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
3 0
3 2
2 1
3 1
5 3
3 1
4 1
5 3
Output
10
1
21
----------------------------------------------------------------------------------------------------
E. Down Below
time limit per test: 5 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
4 4
11 22 13
8 7 5
1 2
2 3
3 4
4 1
4 4
11 22 13
5 7 8
1 2
2 3
3 4
4 1
5 7
10 40 20 30
7 2 10 5
1 2
1 5
2 3
2 4
2 5
3 4
4 5
Output
15
15
19
----------------------------------------------------------------------------------------------------
F. Strange Sort
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
3
3 2 1
7
4 5 7 1 3 2 6
5
1 2 3 4 5
Output
3
5
0
----------------------------------------------------------------------------------------------------
