Problem Statement

You are given a positive integer N.

We have a grid with N rows and N columns, where the square at the i-th row from the top and j-th column from the left has a digit A_{i,j} written on it.

Assume that the upper and lower edges of this grid are connected, as well as the left and right edges. In other words, all of the following holds.

• (N,i) is just above (1,i), and (1,i) is just below (N,i). (1\le i\le N).
• (i,N) is just to the left of (i,1), and (i,1) is just to the right of (i,N). (1\le i\le N).

Takahashi will first choose one of the following eight directions: up, down, left, right, and the four diagonal directions. Then, he will start on a square of his choice and repeat moving one square in the chosen direction N-1 times.

In this process, Takahashi visits N squares. Find the greatest possible value of the integer that is obtained by arranging the digits written on the squares visited by Takahashi from left to right in the order visited by him.

Constraints

• 1 \le N \le 10
• 1 \le A_{i,j} \le 9
• All values in input are integers.

Sample Input 1

4
1161
1119
7111
1811

Sample Output 1

9786

If Takahashi starts on the square at the 2-nd row from the top and 4-th column from the left and goes down and to the right, the integer obtained by arranging the digits written on the visited squares will be 9786. It is impossible to make a value greater than 9786, so the answer is 9786.

Sample Input 2

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

Sample Output 2

1111111111

Note that the answer may not fit into a 32-bit integer.

Problem Statement

This problem is a simplified version of Problem F.

You are given an integer sequence of length N: A = (A_1, A_2, \ldots, A_N).

When splitting A at one position into two non-empty (contiguous) subarrays, find the maximum possible sum of the counts of distinct integers in those subarrays.

More formally, find the maximum sum of the following two values for an integer i such that 1 \leq i \leq N-1: the count of distinct integers in (A_1, A_2, \ldots, A_i), and the count of distinct integers in (A_{i+1}, A_{i+2}, \ldots, A_N).

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq A_i \leq N (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

5

• For i=1, (3) contains 1 distinct integer, and (1,4,1,5) contains 3 distinct integers, for a total of 4.
• For i=2, (3,1) contains 2 distinct integers, and (4,1,5) contains 3 distinct integers, for a total of 5.
• For i=3, (3,1,4) contains 3 distinct integers, and (1,5) contains 2 distinct integers, for a total of 5.
• For i=4, (3,1,4,1) contains 3 distinct integers, and (5) contains 1 distinct integer, for a total of 4.

Therefore, the maximum sum is 5 for i=2,3.

Sample Input 2

10
2 5 6 5 2 1 7 9 7 2

Sample Output 2

8

Problem Statement

There are N people numbered from 1 to N visiting a conveyor belt sushi restaurant. The gourmet level of person i is A_i.

Now, M pieces of sushi will be placed on the conveyor belt. The deliciousness of the j-th sushi is B_j. Each piece of sushi passes in front of people 1, 2, \dots, N in this order. Each person, when a sushi whose deliciousness is not less than their gourmet level passes in front of them, will take and eat that sushi; otherwise, they do nothing. A sushi that person i takes and eats will no longer pass in front of person j\ (j > i).

For each of the M pieces of sushi, determine who eats that sushi, or if nobody eats it.

Constraints

• 1 \leq N, M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq 2 \times 10^5
• All input values are integers.

Sample Input 1

3 3
3 8 2
5 2 1

Sample Output 1

1
3
-1

• For the 1st sushi:
  • It first passes in front of person 1. Since B_1 \geq A_1, person 1 takes and eats it.
  • It will not pass in front of person 2 and 3.
• For the 2nd sushi:
  • It first passes in front of person 1. Since B_2 < A_1, person 1 does nothing.
  • Next, it passes in front of person 2. Since B_2 < A_2, person 2 does nothing.
  • Finally, it passes in front of person 3. Since B_2 \geq A_3, person 3 takes and eats it.
• For the 3rd sushi:
  • It first passes in front of person 1. Since B_3 < A_1, person 1 does nothing.
  • Next, it passes in front of person 2. Since B_3 < A_2, person 2 does nothing.
  • Finally, it passes in front of person 3. Since B_3 < A_3, person 3 does nothing.
  • Therefore, nobody eats this sushi.

Sample Input 2

3 3
1 1 1
1 1 1

Sample Output 2

1
1
1

Sample Input 3

10 5
60 83 76 45 70 91 37 58 94 22
70 39 52 33 18

Sample Output 3

1
7
4
10
-1

Problem Statement

N couples are seated in a line.
Count the number of pairs of couples such that neither couple was originally sitting next to each other, and both couples can end up sitting next to each other by swapping seats among those four people.

There is a sequence A = (A_1, A_2, \dots, A_{2N}) of length 2N. Each of the integers 1, 2, \dots, N appears exactly twice in A.

Find the number of integer pairs (a, b) satisfying 1 \leq a < b \leq N and all of the following conditions:

• The two occurrences of a in A are not adjacent.
• The two occurrences of b in A are not adjacent.
• By performing the following operation one or more times in any order, it is possible to reach a state where the two occurrences of a in A are adjacent and the two occurrences of b in A are also adjacent.
  • Choose an integer pair (i, j) (1 \leq i \leq 2N, 1 \leq j \leq 2N) such that A_i = a and A_j = b, and swap A_i with A_j.

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq N
• Each of 1, 2, \dots, N appears exactly twice in A.
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

3
3
1 2 3 3 1 2
4
1 1 2 2 3 3 4 4
5
1 2 3 4 5 1 2 3 4 5

Sample Output 1

1
0
4

Consider the first test case.
(a, b) = (1, 2) satisfies the conditions in the problem statement, for the following reasons:

• The two occurrences of 1 in A are not adjacent.
• The two occurrences of 2 in A are not adjacent.
• By performing the operation where (i, j) = (1, 6) and swapping A_1 with A_6, you can reach a state where the two occurrences of 1 are adjacent and the two occurrences of 2 are also adjacent.

(1, 2) is the only pair (a, b) that satisfies the conditions.