Codeforces Round 942 (Div. 1)


A. Permutation Counting
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
8
1 10
1
2 4
8 4
3 4
6 1 8
3 9
7 6 2
5 3
6 6 7 4 6
9 7
7 6 1 7 6 2 4 3 3
10 10
1 3 1 2 1 9 3 5 7 5
9 8
5 8 7 5 1 3 2 9 8
Output
11
15
15
22
28
32
28
36
----------------------------------------------------------------------------------------------------
B1. Reverse Card (Easy Version)
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
1 1
2 3
3 5
10 8
100 1233
1000000 1145141
Output
1
3
4
14
153
1643498
----------------------------------------------------------------------------------------------------
B2. Reverse Card (Hard Version)
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
1 1
2 3
3 5
10 8
100 1233
1000000 1145141
Output
0
1
1
6
423
5933961
----------------------------------------------------------------------------------------------------
C. Fenwick Tree
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
8 1
1 2 1 4 1 2 1 8
6 2
1 4 3 17 5 16
Output
1 1 1 1 1 1 1 1
1 2 3 4 5 6
----------------------------------------------------------------------------------------------------
D. Long Way to be Non-decreasing
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
5 8
1 6 3 7 1
2 3 5 8 7 1 5 6
3 3
1 3 2
2 1 3
10 10
2 8 5 4 8 4 1 5 10 10
6 7 2 6 3 4 1 1 3 5
Output
3
-1
3
----------------------------------------------------------------------------------------------------
E1. Again Counting Arrays (Easy Version)
time limit per test: 5 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
6
3 2 1
5 5 3
13 4 1
100 6 7
100 11 3
1000 424 132
Output
6
3120
59982228
943484039
644081522
501350342
----------------------------------------------------------------------------------------------------
E2. Again Counting Arrays (Hard Version)
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
6
3 2 1
5 5 3
13 4 1
100 6 7
100 11 3
1000 424 132
Output
6
3120
59982228
943484039
644081522
501350342
----------------------------------------------------------------------------------------------------
F. Next and Prev
time limit per test: 15 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
1
7
6 1 4 3 2 5 7
1 1
0
1 3
1 2
3 1 2 3
1 3
2 2 6
Output
1
9
8
5
10
14
16
14
30
----------------------------------------------------------------------------------------------------
