1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Sum of Digits of Sums
Contest: Kotlin Heroes: Episode 9 (Unrated, T-Shirts + Prizes!)
Difficulty rating: 2400
Tags: *special, binary search, data structures

You are given an array $$$[a_1, a_2, \dots, a_n]$$$, consisting of positive integers.

For every $$$i$$$ from $$$1$$$ to $$$n$$$, calculate $$$\sum \limits_{j=1}^{n} F(a_i + a_j)$$$, where $$$F(x)$$$ is the sum of digits of $$$x$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i < 10^9$$$).

Output format:
Print $$$n$$$ integers. The $$$i$$$-th of them should be equal to $$$\sum \limits_{j=1}^{n} F(a_i + a_j)$$$.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Example input:
4
1 3 3 7

Example output:
18 17 17 15

Example input:
3
42 1337 999

Example output:
38 53 47

Editorial:
To solve this problem, we can use the fact that the sum of digits of $$$x+y$$$ is equal to $$$F(x) + F(y) - 9 \cdot c$$$, where $$$c$$$ is the number of digits where the result of the addition was carried over to the next digit. So, to calculate the answer for $$$a_i$$$, we have to consider each digit and calculate the number of values of $$$a_j$$$ such that, when $$$a_i + a_j$$$ is calculated, this digit is carried over to the next digit.
For the lowest digit, it is quite easy: you have to consider if the sum of the last digit of $$$a_i$$$ and $$$a_j$$$ is greater than or equal to $$$10$$$. But for all other digits, it is way more difficult, because carrying from lower digits may affect higher digits.
However, there is a simple way to avoid dealing with any carrying from lower digits. Suppose that we have to check that when we compute $$$a_i + a_j$$$, a carry happens from the $$$k$$$-th digit to the $$$k+1$$$-th digit. Let's consider both numbers modulo $$$10^k$$$ (i. e. consider $$$a_i \bmod 10^{k+1}$$$ and $$$a_j \bmod 10^{k+1}$$$). If the sum of these two numbers has more than $$$k$$$ digits, then a carry happens in the respective position.
So, for the fixed $$$a_i$$$ and $$$k$$$, we should find the number of integers $$$a_j$$$ such that $$$a_i \bmod 10^{k+1} + a_j \bmod 10^{k+1} \ge 10^{k+1}$$$. In order to do it fast, for every $$$k$$$, we can prepare a sorted list of remainders modulo $$$10^{k}$$$, and then use binary search to calculate the number of integers that are greater than or equal to $$$10^{k+1} - a_i \bmod 10^{k+1}$$$; this is exactly the number of integers $$$a_j$$$ such that computing $$$a_i + a_j$$$ requires a carry in the $$$k$$$-th digit.
Note that the standard binary search function in Kotlin does not necessarily return the leftmost of equal elements, so you probably should implement your own binary search or make sure that no element meets the binary search criteria (as it is done in the solution by Pavel Kunyavskiy).
Solution complexity: $$$O(n \log n \log A$$$).
Circle Coloring
Contest: Grakn Forces 2020
Difficulty rating: 800
Tags: constructive algorithms

You are given three sequences: $$$a_1, a_2, \ldots, a_n$$$; $$$b_1, b_2, \ldots, b_n$$$; $$$c_1, c_2, \ldots, c_n$$$.

For each $$$i$$$, $$$a_i \neq b_i$$$, $$$a_i \neq c_i$$$, $$$b_i \neq c_i$$$.

Find a sequence $$$p_1, p_2, \ldots, p_n$$$, that satisfy the following conditions:

- $$$p_i \in \{a_i, b_i, c_i\}$$$
- $$$p_i \neq p_{(i \mod n) + 1}$$$.

In other words, for each element, you need to choose one of the three possible values, such that no two adjacent elements (where we consider elements $$$i,i+1$$$ adjacent for $$$i<n$$$ and also elements $$$1$$$ and $$$n$$$) will have equal value.

It can be proved that in the given constraints solution always exists. You don't need to minimize/maximize anything, you need to find any proper sequence.

Input format:
The first line of input contains one integer $$$t$$$ ($$$1 \leq t \leq 100$$$): the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$3 \leq n \leq 100$$$): the number of elements in the given sequences.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 100$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 100$$$).

The fourth line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_i \leq 100$$$).

It is guaranteed that $$$a_i \neq b_i$$$, $$$a_i \neq c_i$$$, $$$b_i \neq c_i$$$ for all $$$i$$$.

Output format:
For each test case, print $$$n$$$ integers: $$$p_1, p_2, \ldots, p_n$$$ ($$$p_i \in \{a_i, b_i, c_i\}$$$, $$$p_i \neq p_{i \mod n + 1}$$$).

If there are several solutions, you can print any.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case $$$p = [1, 2, 3]$$$.

It is a correct answer, because:

- $$$p_1 = 1 = a_1$$$, $$$p_2 = 2 = b_2$$$, $$$p_3 = 3 = c_3$$$
- $$$p_1 \neq p_2 $$$, $$$p_2 \neq p_3 $$$, $$$p_3 \neq p_1$$$

All possible correct answers to this test case are: $$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 1, 3]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 2]$$$, $$$[3, 2, 1]$$$.

In the second test case $$$p = [1, 2, 1, 2]$$$.

In this sequence $$$p_1 = a_1$$$, $$$p_2 = a_2$$$, $$$p_3 = a_3$$$, $$$p_4 = a_4$$$. Also we can see, that no two adjacent elements of the sequence are equal.

In the third test case $$$p = [1, 3, 4, 3, 2, 4, 2]$$$.

In this sequence $$$p_1 = a_1$$$, $$$p_2 = a_2$$$, $$$p_3 = b_3$$$, $$$p_4 = b_4$$$, $$$p_5 = b_5$$$, $$$p_6 = c_6$$$, $$$p_7 = c_7$$$. Also we can see, that no two adjacent elements of the sequence are equal.

Example input:
5
3
1 1 1
2 2 2
3 3 3
4
1 2 1 2
2 1 2 1
3 4 3 4
7
1 3 3 1 1 1 1
2 4 4 3 2 2 4
4 2 2 2 4 4 2
3
1 2 1
2 3 3
3 1 2
10
1 1 1 2 2 2 3 3 3 1
2 2 2 3 3 3 1 1 1 2
3 3 3 1 1 1 2 2 2 3

Example output:
1 2 3
1 2 1 2
1 3 4 3 2 4 2
1 3 2
1 2 3 1 2 3 1 2 3 2

Editorial:
At first, set $$$p_1 = a_1$$$.
Then for $$$i \in \{2, \ldots, n-1\}$$$ if $$$a_i = p_{i-1}$$$, then set $$$p_i = b_i$$$. Otherwise, set $$$p_i = a_i$$$.
In the end, set $$$p_n$$$ to one of $$$\{a_n, b_n, c_n\}$$$, which is not equal to $$$p_1$$$ or $$$p_{n-1}$$$.
Arrays Sum
Contest: Grakn Forces 2020
Difficulty rating: 1400
Tags: constructive algorithms, greedy, math

You are given a non-decreasing array of non-negative integers $$$a_1, a_2, \ldots, a_n$$$. Also you are given a positive integer $$$k$$$.

You want to find $$$m$$$ non-decreasing arrays of non-negative integers $$$b_1, b_2, \ldots, b_m$$$, such that:

- The size of $$$b_i$$$ is equal to $$$n$$$ for all $$$1 \leq i \leq m$$$.
- For all $$$1 \leq j \leq n$$$, $$$a_j = b_{1, j} + b_{2, j} + \ldots + b_{m, j}$$$. In the other word, array $$$a$$$ is the sum of arrays $$$b_i$$$.
- The number of different elements in the array $$$b_i$$$ is at most $$$k$$$ for all $$$1 \leq i \leq m$$$.

Find the minimum possible value of $$$m$$$, or report that there is no possible $$$m$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 100$$$): the number of test cases.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1 \leq n \leq 100$$$, $$$1 \leq k \leq n$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq 100$$$, $$$a_n > 0$$$).

Output format:
For each test case print a single integer: the minimum possible value of $$$m$$$. If there is no such $$$m$$$, print $$$-1$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, there is no possible $$$m$$$, because all elements of all arrays should be equal to $$$0$$$. But in this case, it is impossible to get $$$a_4 = 1$$$ as the sum of zeros.

In the second test case, we can take $$$b_1 = [3, 3, 3]$$$. $$$1$$$ is the smallest possible value of $$$m$$$.

In the third test case, we can take $$$b_1 = [0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2]$$$ and $$$b_2 = [0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2]$$$. It's easy to see, that $$$a_i = b_{1, i} + b_{2, i}$$$ for all $$$i$$$ and the number of different elements in $$$b_1$$$ and in $$$b_2$$$ is equal to $$$3$$$ (so it is at most $$$3$$$). It can be proven that $$$2$$$ is the smallest possible value of $$$m$$$.

Example input:
6
4 1
0 0 0 1
3 1
3 3 3
11 3
0 1 2 2 3 3 3 4 4 4 4
5 3
1 2 3 4 5
9 4
2 2 3 5 7 11 13 13 17
10 7
0 1 1 2 3 3 4 5 5 6

Example output:
-1
1
2
2
2
1

Editorial:
Case $$$k = 1$$$:
If all $$$a_i$$$ are equal the answer is $$$1$$$.
Otherwise the answer is $$$-1$$$.
Case $$$k > 1$$$:
Let's consider an array $$$a' = (a_2 - a_1, a_3 - a_2, \ldots, a_n - a_{n-1})$$$ and arrays $$$b_i' = (b_{i, 2} - b_{i, 1}, b_{i, 3} - b_{i, 2}, \ldots, b_{i, n} - b_{i, n-1})$$$.
The number of non-zero elements in $$$b_i'$$$ is at most $$$k-1$$$.
Let's define $$$c$$$ as the number of non-zero elements in $$$a'$$$ or in the other words the number of indices $$$i$$$, such that $$$a_i \neq a_{i+1}$$$.
The answer is at least $$$\lceil \frac{c}{k-1} \rceil$$$. It's easy to prove that there exists arrays $$$b_i$$$ with such number $$$m$$$.
Searchlights
Contest: Grakn Forces 2020
Difficulty rating: 2000
Tags: binary search, brute force, data structures, dp, implementation, sortings, two pointers

There are $$$n$$$ robbers at coordinates $$$(a_1, b_1)$$$, $$$(a_2, b_2)$$$, ..., $$$(a_n, b_n)$$$ and $$$m$$$ searchlight at coordinates $$$(c_1, d_1)$$$, $$$(c_2, d_2)$$$, ..., $$$(c_m, d_m)$$$.

In one move you can move each robber to the right (increase $$$a_i$$$ of each robber by one) or move each robber up (increase $$$b_i$$$ of each robber by one). Note that you should either increase all $$$a_i$$$ or all $$$b_i$$$, you can't increase $$$a_i$$$ for some points and $$$b_i$$$ for some other points.

Searchlight $$$j$$$ can see a robber $$$i$$$ if $$$a_i \leq c_j$$$ and $$$b_i \leq d_j$$$.

A configuration of robbers is safe if no searchlight can see a robber (i.e. if there is no pair $$$i,j$$$ such that searchlight $$$j$$$ can see a robber $$$i$$$).

What is the minimum number of moves you need to perform to reach a safe configuration?

Input format:
The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 2000$$$): the number of robbers and the number of searchlight.

Each of the next $$$n$$$ lines contains two integers $$$a_i$$$, $$$b_i$$$ ($$$0 \leq a_i, b_i \leq 10^6$$$), coordinates of robbers.

Each of the next $$$m$$$ lines contains two integers $$$c_i$$$, $$$d_i$$$ ($$$0 \leq c_i, d_i \leq 10^6$$$), coordinates of searchlights.

Output format:
Print one integer: the minimum number of moves you need to perform to reach a safe configuration.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test, you can move each robber to the right three times. After that there will be one robber in the coordinates $$$(3, 0)$$$.

The configuration of the robbers is safe, because the only searchlight can't see the robber, because it is in the coordinates $$$(2, 3)$$$ and $$$3 > 2$$$.

In the second test, you can move each robber to the right two times and two times up. After that robbers will be in the coordinates $$$(3, 8)$$$, $$$(8, 3)$$$.

It's easy the see that the configuration of the robbers is safe.

It can be proved that you can't reach a safe configuration using no more than $$$3$$$ moves.

Example input:
1 1
0 0
2 3

Example output:
3

Example input:
2 3
1 6
6 1
10 1
1 10
7 7

Example output:
4

Editorial:
Let's define as $$$x$$$ our move to the right and as $$$y$$$ our move to the up. For all pairs $$$(i, j)$$$ of (robber, searchlight) at least one of this should be true: $$$x + a_i > c_j$$$, $$$y + b_i > d_j$$$. So if $$$x \leq c_j - a_i$$$ then $$$y \geq d_j - b_i + 1$$$.
Let's make an array $$$r$$$ of length $$$C = 10^6$$$ and write on each position of $$$x$$$ the minimum value of $$$y$$$. For each $$$(i, j)$$$ we should make $$$r_x = max(r_x, d_j - b_i + 1)$$$ for all $$$x \leq c_j - a_i$$$. So we have $$$nm$$$ queries of $$$max=$$$ on prefix. We can do it using suffix maximums. After we will calculate all $$$a_x$$$ the answer is $$$\min\limits_{x}{(x + r_x)}$$$.
Time complexity: $$$O(nm + C)$$$.
Two Different
Contest: Grakn Forces 2020
Difficulty rating: 2300
Tags: constructive algorithms, divide and conquer

You are given an integer $$$n$$$.

You should find a list of pairs $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$, ..., $$$(x_q, y_q)$$$ ($$$1 \leq x_i, y_i \leq n$$$) satisfying the following condition.

Let's consider some function $$$f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$$$ (we define $$$\mathbb{N}$$$ as the set of positive integers). In other words, $$$f$$$ is a function that returns a positive integer for a pair of positive integers.

Let's make an array $$$a_1, a_2, \ldots, a_n$$$, where $$$a_i = i$$$ initially.

You will perform $$$q$$$ operations, in $$$i$$$-th of them you will:

1. assign $$$t = f(a_{x_i}, a_{y_i})$$$ ($$$t$$$ is a temporary variable, it is used only for the next two assignments);
2. assign $$$a_{x_i} = t$$$;
3. assign $$$a_{y_i} = t$$$.

In other words, you need to simultaneously change $$$a_{x_i}$$$ and $$$a_{y_i}$$$ to $$$f(a_{x_i}, a_{y_i})$$$. Note that during this process $$$f(p, q)$$$ is always the same for a fixed pair of $$$p$$$ and $$$q$$$.

In the end, there should be at most two different numbers in the array $$$a$$$.

It should be true for any function $$$f$$$.

Find any possible list of pairs. The number of pairs should not exceed $$$5 \cdot 10^5$$$.

Input format:
The single line contains a single integer $$$n$$$ ($$$1 \leq n \leq 15\,000$$$).

Output format:
In the first line print $$$q$$$ ($$$0 \leq q \leq 5 \cdot 10^5$$$) — the number of pairs.

In each of the next $$$q$$$ lines print two integers. In the $$$i$$$-th line print $$$x_i$$$, $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$).

The condition described in the statement should be satisfied.

If there exists multiple answers you can print any of them.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example, after performing the only operation the array $$$a$$$ will be $$$[f(a_1, a_2), f(a_1, a_2), a_3]$$$. It will always have at most two different numbers.

In the second example, after performing two operations the array $$$a$$$ will be $$$[f(a_1, a_2), f(a_1, a_2), f(a_3, a_4), f(a_3, a_4)]$$$. It will always have at most two different numbers.

Example input:
3

Example output:
1
1 2

Example input:
4

Example output:
2
1 2
3 4

Editorial:
Claim: for each $$$k$$$, we can perform operations on $$$2^k$$$ elements to make all numbers the same.
You can prove this fact with induction by $$$k$$$. For $$$k=0$$$ this fact is obvious, For $$$k>0$$$, at first change first $$$2^{k-1}$$$ and last $$$2^{k-1}$$$ points to the same value (assume that those values are $$$x$$$ and $$$y$$$, respectively). And then, perform operations on points $$$i$$$ and $$$i + 2^{k-1}$$$, to simultaneously change them to $$$f(x,y)$$$. After that, all values will be equal $$$\blacksquare$$$.
Using this observation, it is easy to leave only two different values in the array. Find the maximum $$$2^k \leq n$$$, and then change first $$$2^k$$$ numbers to the same number, and then change last $$$2^k$$$ elements to the same number (note that $$$2^k + 2^k > n$$$, so in the end there will be only two different elements).
Clusterization Counting
Contest: Grakn Forces 2020
Difficulty rating: 2700
Tags: combinatorics, dp, dsu, fft, graphs, trees

There are $$$n$$$ computers in the company network. They are numbered from $$$1$$$ to $$$n$$$.

For each pair of two computers $$$1 \leq i < j \leq n$$$ you know the value $$$a_{i,j}$$$: the difficulty of sending data between computers $$$i$$$ and $$$j$$$. All values $$$a_{i,j}$$$ for $$$i<j$$$ are different.

You want to separate all computers into $$$k$$$ sets $$$A_1, A_2, \ldots, A_k$$$, such that the following conditions are satisfied:

- for each computer $$$1 \leq i \leq n$$$ there is exactly one set $$$A_j$$$, such that $$$i \in A_j$$$;
- for each two pairs of computers $$$(s, f)$$$ and $$$(x, y)$$$ ($$$s \neq f$$$, $$$x \neq y$$$), such that $$$s$$$, $$$f$$$, $$$x$$$ are from the same set but $$$x$$$ and $$$y$$$ are from different sets, $$$a_{s,f} < a_{x,y}$$$.

For each $$$1 \leq k \leq n$$$ find the number of ways to divide computers into $$$k$$$ groups, such that all required conditions are satisfied. These values can be large, so you need to find them by modulo $$$998\,244\,353$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 1500$$$): the number of computers.

The $$$i$$$-th of the next $$$n$$$ lines contains $$$n$$$ integers $$$a_{i,1}, a_{i,2}, \ldots, a_{i,n}$$$($$$0 \leq a_{i,j} \leq \frac{n (n-1)}{2}$$$).

It is guaranteed that:

- for all $$$1 \leq i \leq n$$$ $$$a_{i,i} = 0$$$;
- for all $$$1 \leq i < j \leq n$$$ $$$a_{i,j} > 0$$$;
- for all $$$1 \leq i < j \leq n$$$ $$$a_{i,j} = a_{j,i}$$$;
- all $$$a_{i,j}$$$ for $$$i <j$$$ are different.

Output format:
Print $$$n$$$ integers: the $$$k$$$-th of them should be equal to the number of possible ways to divide computers into $$$k$$$ groups, such that all required conditions are satisfied, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
Here are all possible ways to separate all computers into $$$4$$$ groups in the second example:

- $$$\{1, 2\}, \{3, 4\}, \{5\}, \{6, 7\}$$$;
- $$$\{1\}, \{2\}, \{3, 4\}, \{5, 6, 7\}$$$;
- $$$\{1, 2\}, \{3\}, \{4\}, \{5, 6, 7\}$$$.

Example input:
4
0 3 4 6
3 0 2 1
4 2 0 5
6 1 5 0

Example output:
1 0 1 1

Example input:
7
0 1 18 15 19 12 21
1 0 16 13 17 20 14
18 16 0 2 7 10 9
15 13 2 0 6 8 11
19 17 7 6 0 4 5
12 20 10 8 4 0 3
21 14 9 11 5 3 0

Example output:
1 1 2 3 4 3 1

Editorial:
Sort all edges by their weights.
In this order, maintain the DSU. For each connected component, let's maintain $$$dp_k$$$: the number of ways to divide this component into $$$k$$$ groups. When you merge two connected clusters, you have to recalculate the DP as in the multiplication of two polynomials (of course, if you bound $$$k$$$ by the size of the connected component, similarly to the similar tree DP's, it works in $$$O(n^2)$$$ total).
Once some connected component becomes a clique, then we obtain a new cluster, and you should increase $$$dp_1$$$ for this connected component by $$$1$$$.
Jellyfish and Math
Contest: Codeforces Round 901 (Div. 1)
Difficulty rating: 2400
Tags: bitmasks, brute force, dfs and similar, dp, graphs, shortest paths

Jellyfish is given the non-negative integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ and $$$m$$$. Initially $$$(x,y)=(a,b)$$$. Jellyfish wants to do several operations so that $$$(x,y)=(c,d)$$$.

For each operation, she can do one of the following:

- $$$x := x\,\&\,y$$$,
- $$$x := x\,|\,y$$$,
- $$$y := x \oplus y$$$,
- $$$y := y \oplus m$$$.

Here $$$\&$$$ denotes the bitwise AND operation, $$$|$$$ denotes the bitwise OR operation and $$$\oplus$$$ denotes the bitwise XOR operation.

Now Jellyfish asks you for the minimum number of operations such that $$$(x,y)=(c,d)$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^5$$$). The description of the test cases follows.

The only line of each test case contains five integers, $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ and $$$m$$$ ($$$0 \leq a, b, c, d, m < 2^{30}$$$).

Output format:
For each test case, output a single integer — the minimum number of operations. If this cannot be achieved, output $$$-1$$$ instead.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, we can do the operation $$$y = x \oplus y$$$.

In the second test case, it is not possible to change $$$(x,y)=(1,2)$$$ using any sequence of operations.

In the third test case, we can do the operation $$$x = x\,\&\,y$$$ followed by the operation $$$y = y \oplus m$$$.

Example input:
10
1 0 1 1 1
3 3 1 2 1
1 6 0 7 1
2 4 4 9 8
21 4 0 17 28
50 50 0 0 39
95 33 1 33 110
138 202 174 64 108
78 340 68 340 461
457 291 491 566 766

Example output:
1
-1
2
-1
-1
2
1
4
1
3

Editorial:
Jellyfish and OEIS
Contest: Codeforces Round 901 (Div. 1)
Difficulty rating: 3500
Tags: dp

Jellyfish always uses OEIS to solve math problems, but now she finds a problem that cannot be solved by OEIS:

Count the number of permutations $$$p$$$ of $$$[1, 2, \dots, n]$$$ such that for all $$$(l, r)$$$ such that $$$l \leq r \leq m_l$$$, the subarray $$$[p_l, p_{l+1}, \dots, p_r]$$$ is not a permutation of $$$[l, l+1, \dots, r]$$$.

Since the answer may be large, you only need to find the answer modulo $$$10^9+7$$$.

Input format:
The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 200$$$) — the length of the permutation.

The second line of the input contains $$$n$$$ integers $$$m_1, m_2, \dots, m_n$$$ ($$$0 \leq m_i \leq n$$$).

Output format:
Output the number of different permutations that satisfy the conditions, modulo $$$10^9+7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example, $$$[2, 3, 1]$$$ and $$$[3, 1, 2]$$$ satisfies the condition.

Example input:
3
1 2 3

Example output:
2

Example input:
5
2 4 3 4 5

Example output:
38

Editorial:
Let's call a section $$$[l, r]$$$ bad if $$$p_l, p_{l+1}, \dots, p_{r-1}, p_r$$$ is a permutation of $$$l, l + 1, \dots, r - 1, r$$$ and $$$l \leq r \leq m_l$$$.
Let's call a section $$$[l, r]$$$ primitive if it's a bad section and there are no section $$$[l', r']$$$ satisfying $$$[l', r']$$$ is also a bad section and $$$[l, r]$$$ covers $$$[l', r']$$$.
Then we will find for all primitive, none of them intersect.
Because if $$$[l_1, r_1]$$$ is a bad section, $$$[l_2, r_2]$$$ is a bad section, $$$l_1 < l_2 < r_1 < r_2$$$, the section $$$[l_2, r_1]$$$ will also be a bad section, but both $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ covers $$$[l_2, r_1]$$$.
Let's use Principle of inclusion-exclusion and dynamic programming to solve the problem.
Let's define $$$f(l, r)$$$ as the number of $$$p_l, p_{l+1}, \dots, p_{r-1}, p_r$$$ which is a primitive section. By the Principle of inclusion-exclusion, we count the ways to fix $$$k$$$ primitive sections in range $$$[l, r]$$$, and arrange the rest arbitrarily.
Then we can define $$$g_{1/2}(l, r, x)$$$ as the number of ways to fix $$$k$$$ ($$$k$$$ is odd/even) primitive sections in range $$$[l, r]$$$, and the number of the positions which doesn't cover by any primitive section is $$$x$$$.
Finally, we define $$$g(l, r, x) = g_2(l, r, x) - g_1(l, r, x)$$$, We will have the following transition:
$$$\forall l \leq r \leq m_l, f(l, r) = \sum_{x=0}^{r-l+1} g(l, r, x) \times x!$$$
$$$g(l, r, x) = g(l, r - 1, x - 1) - \sum_{mid=l}^r g(l, mid - 1, x )\times f(mid, r)$$$
In the above we think $$$g(i, i-1, 0)=1$$$.
Tips: In fact there are some bugs in the transition, because after we get $$$f(l, r)$$$, we will add $$$-f(l, r)$$$ to $$$g(l, r, 0)$$$. The above transfers are sequential, specific implementation details require your own attention.
$$$\sum_{x=0}^{n} g(1, n, x) \times x!$$$ is the answer we need.
Time complexity: $$$O(n^4)$$$