Problem Statement

You are given a sequence of integers A = (A_1, A_2, A_3).
Let B = (B_1, B_2, B_3) be any permutation of A.
Determine whether it is possible that B_1 \times B_2 = B_3.

Constraints

• All input values are integers.
• 1 \le A_1, A_2, A_3 \le 100

Sample Input 1

3 15 5

Sample Output 1

Yes

Here, A=(3,15,5). By rearranging it as B=(3,5,15), we can satisfy B_1 \times B_2 = B_3.

Sample Input 2

5 3 2

Sample Output 2

No

No permutation of B satisfies B_1 \times B_2 = B_3.

Problem Statement

You are given a sequence of M integers A = (A_1, A_2, \dots, A_M).
Each element of A is an integer between 1 and N, inclusive, and all elements are distinct.

List all integers between 1 and N that do not appear in A in ascending order.

Constraints

• All input values are integers.
• 1 \le M \le N \le 1000
• 1 \le A_i \le N
• The elements of A are distinct.

Sample Input 1

10 3
3 9 2

Sample Output 1

7
1 4 5 6 7 8 10

Here, A=(3,9,2).
The integers between 1 and 10 that do not appear in A, listed in ascending order, are 1,4,5,6,7,8,10.

Sample Input 2

6 6
1 3 5 2 4 6

Sample Output 2

0

No integer between 1 and 6 is missing from A.
In this case, print 0 on the first line and leave the second line empty.

Sample Input 3

9 1
9

Sample Output 3

8
1 2 3 4 5 6 7 8

Problem Statement

There are N people numbered from 1 to N.

Person i is wearing a bib with the number Q_i and is staring at person P_i.

For each i = 1,2,\ldots,N, find the number written on the bib of the person that the person wearing the bib with number i is staring at.

Constraints

• 2 \leq N \leq 3\times 10^5
• 1 \leq P_i \leq N
• The values of P_i are distinct.
• 1 \leq Q_i \leq N
• The values of Q_i are distinct.
• All input values are integers.

Sample Input 1

4
4 3 2 1
2 3 1 4

Sample Output 1

3 4 1 2

Person 3 is wearing the bib with the number 1, and the person that person 3 is staring at, person 2, is wearing the bib with the number 3. Thus, the answer for i = 1 is 3.

Sample Input 2

10
2 6 4 3 7 8 9 10 1 5
1 4 8 2 10 5 7 3 9 6

Sample Output 2

4 8 6 5 3 10 9 2 1 7

Problem Statement

There are N dice. The i-th die has K_i faces, with the numbers A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} written on them. When you roll this die, each face appears with probability \frac{1}{K_i}.

You choose two dice from the N dice and roll them. Determine the maximum probability that the two dice show the same number, when the dice are chosen optimally.

Constraints

• 2 \leq N \leq 100
• 1 \leq K_i
• K_1 + K_2 + \dots + K_N \leq 10^5
• 1 \leq A_{i,j} \leq 10^5
• All input values are integers.

Sample Input 1

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

Sample Output 1

0.333333333333333

• When choosing the 1st and 2nd dice, the probability that the outcomes are the same is \frac{1}{3}.
• When choosing the 1st and 3rd dice, the probability is \frac{1}{6}.
• When choosing the 2nd and 3rd dice, the probability is \frac{1}{6}.

Therefore, the maximum probability is \frac{1}{3} = 0.3333333333\ldots.

Sample Input 2

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

Sample Output 2

0.666666666666667

Problem Statement

There are N servers numbered from 1 to N and M cables numbered from 1 to M.
Cable i connects servers A_i and B_i bidirectionally.

By performing the following operation some number of times (possibly zero), make all servers connected via cables.

• Operation: Choose one cable and reconnect one of its ends to a different server.

Find the minimum number of operations required and output an operation sequence achieving this minimum.

Constraints

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

Sample Input 1

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

Sample Output 1

1
1 1 3

By reconnecting the end of cable 1 that is connected to server 1 to server 3, the servers can be connected via cables.

Operations such as reconnecting the end of cable 5 that is connected to server 4 to server 1, or reconnecting the end of cable 2 that is connected to server 2 to server 3, will also result in all servers being connected and are considered correct.

Sample Input 2

4 3
3 4
4 1
1 2

Sample Output 2

0

No operation may be necessary.

Sample Input 3

5 4
3 3
3 3
3 3
3 3

Sample Output 3

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

Problem Statement

There is an empty array A. For i = 1,2,\ldots,N, perform the following operation in order:

• Insert the number i into A so that it becomes the P_i-th element from the beginning.
  • More precisely, replace A with the concatenation of the first P_i-1 elements of A, then i, then the remaining elements of A starting from the P_i-th element, in this order.

Output the final array A after all operations have been completed.

Constraints

• 1 \leq N \leq 5\times 10^5
• 1 \leq P_i \leq i
• All input values are integers.

Sample Input 1

4
1 1 2 1

Sample Output 1

4 2 3 1

The operations are performed as follows:

• Insert the number 1 so that it becomes the 1st element of A. Now, A = (1).
• Insert the number 2 so that it becomes the 1st element of A. Now, A = (2, 1).
• Insert the number 3 so that it becomes the 2nd element of A. Now, A = (2, 3, 1).
• Insert the number 4 so that it becomes the 1st element of A. Now, A = (4, 2, 3, 1).

Sample Input 2

5
1 2 3 4 5

Sample Output 2

1 2 3 4 5

Problem Statement

For integers A, B, C ( A < B < C ), if they satisfy B-A = C-B, then (A, B, C) is called a fine triplet.
You are given a set of N distinct positive integers S = \{ S_1, S_2, \dots, S_N \}. Find the number of fine triplets (A, B, C) with A, B, C \in S.

Constraints

• All input values are integers.
• 1 \le N \le 10^6
• 1 \le S_i \le 10^6
• The elements of S are distinct.

Sample Input 1

5
8 3 1 5 2

Sample Output 1

3

Here, S = \{8,3,1,5,2\}. The fine triplets to be counted are the following three:

• (1,2,3)
• (1,3,5)
• (2,5,8)

Sample Input 2

7
300000 100000 499998 499999 200000 400000 500000

Sample Output 2

5

Sample Input 3

10
13 1 16 15 12 4 7 10 2 19

Sample Output 3

10