We can observe that result cannot exceed 201 — Awruk gets at least 101 votes from one person and Elodreip cannot get more than 100 votes from one person. So we can iterate over every possible integer from 1 to 201 and check if Awruk wins with k set to this integer. We have to remember that k — a_i is always at least 0, so we have to check this condition too. Complexity O(n * M), where M denotes maximum possible value of a_i. Try to solve it in O(n).

First, let's observe that we can replace array a_i with array b_i = a_i  -  a_i - 1, because all we care about are differences between neighboring elements. Now, we can see that our lost array can have length d if and only if for every j such that j  +  d  ≤  n, b_j  =  b_j + d. So we can iterate over every possible d from 1 to n and check if it is correct in O(n). Complexity of whole algorithm is O(n²).

Basically in problem we are given a word in which for every i we can reverse prefix of first i elements and we want to get the smallest lexicographically word. We will show that we can always achieve word in form a^jbn - j.

Let's say that we solved our problem for prefix of length i and for this prefix we have word a^jbi - j (at the beginning it's just empty word). If our next letter is b then we do nothing, because we will get word a^{jbi - j + 1} which is still the smallest lexicographically word. Otherwise we want to reverse prefix of length i, add letter a and reverse prefix of length i  +  1, so we get a word a^j + 1b^i - j, which is still fine for us.

There is still a problem — what if we have already reversed prefix i and we just said that we will reverse it second time. But instead of reversing it second time, we can deny it's first reverse.

Final complexity is O(n).

Deleting prefix and suffix is nothing more than taking a subarray. If subarray is common for all permutations then it has to appear in first permutation. We renumber all permutations such that first permutation is 1, 2, ..., n  -  1, n.

Now for every i in every permutation we count how long is subarray starting at i which looks like i, i  +  1, ..., i  +  k. It can be easily done in O(n) for one permutation with two pointers technique.

Now for every element i we compute reach$[i]$ equal the longest subarray starting in i which looks like i, i  +  1, ..., i  +  k and it apears in all subarrays. It is just minimum over previously calculated values for all permutations.

Now we can see that our result is . Final complexity O(nm).

Let's compute result if there are no edges, we can add them later. If there are no edges then result for pair (i, j) is min(x_i  +  y_j, x_j  +  y_i). First let's fix i for which we want to compute result. Then calculate result with all pairs j such that x_i  +  y_j  ≤  x_j  +  y_i. After some transformations we get that x_i  -  y_i  ≤  x_j  -  y_j. Similarly we have that y_i  +  x_j  <  x_i  +  y_j if x_i  -  y_i  >  y_j  -  x_j.

So let's sort over differences of x_i  -  y_i and compute prefix sums of x_i and suffix sums of y_i. Now we can compute for every i result in O(1). Then we can iterate over every edge (u, v) and subtract min(x_u  +  y_v, x_v  +  y_u) from result of u and v.

Complexity O(nlogn).

First let's observe that if there exists valid subset then it's size is at most 7 (because product of 7 smallest primes is bigger then 3 * 10⁵). Let's define dp[i][j] — number of ways to pick i different elements such that their gcd is equal to j. We can use inclusion--exclusion principle to calculate it. Then dp[i][j] = — , where cnt_j denotes number of a_i such that j | a_i. Because for k  >  3 * 10⁵, dp[i][k]  =  0 we have to check only k  ≤  3 * 10⁵.

Our answer is the smallest i such that dp[i][1] is non-zero. Since dp[i][j] can be quite big we should compute it modulo some big prime.

Final complexity is O(logM * (n + M)), where M is equal to maximum of a_i.