Problem Statement

You are given a sequence a = (a_1, \dots, a_N) of length N consisting of integers between 1 and N.

Find the number of pairs of integers i, j that satisfy all of the following conditions:

• 1 \leq i \lt j \leq N
• \min(a_i, a_j) = i
• \max(a_i, a_j) = j

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq a_i \leq N \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

4
1 3 2 4

Sample Output 1

2

(i, j) = (1, 4), (2, 3) satisfy the conditions.

Sample Input 2

10
5 8 2 2 1 6 7 2 9 10

Sample Output 2

8

Problem Statement

You are given two sequences, each of length N, consisting of integers: A=(A_1, \ldots, A_N) and B=(B_1, \ldots, B_N).

Determine whether there is a sequence of length N, X=(X_1, \ldots, X_N), satisfying all of the conditions below.

• X_i = A_i or X_i = B_i, for every i(1\leq i\leq N).

• |X_i - X_{i+1}| \leq K, for every i(1\leq i\leq N-1).

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq K \leq 10^9
• 1 \leq A_i,B_i \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes

X=(9,6,3,7,5) satisfies all conditions.

Sample Input 2

4 90
1 1 1 100
1 2 3 100

Sample Output 2

No

No X satisfies all conditions.

Sample Input 3

4 1000000000
1 1 1000000000 1000000000
1 1000000000 1 1000000000

Sample Output 3

Yes

Problem Statement

You are given an integer K greater than or equal to 2.
Find the minimum positive integer N such that N! is a multiple of K.

Here, N! denotes the factorial of N. Under the Constraints of this problem, we can prove that such an N always exists.

Constraints

• 2\leq K\leq 10^{12}
• K is an integer.

Sample Input 1

30

Sample Output 1

5

• 1!=1
• 2!=2\times 1=2
• 3!=3\times 2\times 1=6
• 4!=4\times 3\times 2\times 1=24
• 5!=5\times 4\times 3\times 2\times 1=120

Therefore, 5 is the minimum positive integer N such that N! is a multiple of 30. Thus, 5 should be printed.

Sample Input 2

123456789011

Sample Output 2

123456789011

Sample Input 3

280

Sample Output 3

7

Problem Statement

You are given a sequence of integers A = (A_1, A_2, \ldots, A_N) of length N. Define f(l, r) as:

• the number of distinct values in the subsequence (A_l, A_{l+1}, \ldots, A_r).

Evaluate the following expression:

Constraints

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

Sample Input 1

3
1 2 2

Sample Output 1

8

Consider f(1,2). The subsequence (A_1, A_2) = (1,2) contains 2 distinct values, so f(1,2)=2.

Consider f(2,3). The subsequence (A_2, A_3) = (2,2) contains 1 distinct value, so f(2,3)=1.

The sum of f is 8.

Sample Input 2

9
5 4 2 2 3 2 4 4 1

Sample Output 2

111

Problem Statement

For a permutation P = (p_1, p_2, \dots, p_N) of (1,2, \dots, N), let us define the score S(P) of P as follows.

• There are N people, numbered 1,2,\dots,N. Additionally, Snuke is there. Initially, Person i (1 \leq i \leq N) has Ball i.
  Each time Snuke screams, every Person i such that i \neq p_i gives their ball to Person p_i simultaneously.
  If, after screaming at least once, every Person i has Ball i, Snuke stops screaming.
  The score is the number of times Snuke screams until he stops. Here, it is guaranteed that the score will be a finite value.

There are N! permutations P of (1,2, \dots, N). Find the sum, modulo 998244353, of the scores of those permutations, each raised to the K-th power.

• Formally, let S_N be the set of the permutations of (1,2, \dots, N). Compute the following: \displaystyle \left(\sum_{P \in S_N} S(P)^K \right) \bmod {998244353}.

Constraints

• 2 \leq N \leq 50
• 1 \leq K \leq 10^4
• All values in input are integers.

Sample Input 1

2 2

Sample Output 1

5

When N = 2, there are two possible permutations P: (1,2),(2,1).

The score of the permutation (1,2) is found as follows.

• Initially, Person 1 has Ball 1, and Person 2 has Ball 2.
  After Snuke's first scream, Person 1 has Ball 1, and Person 2 has Ball 2.
  Here, every Person i has Ball i, so he stops screaming.
  Thus, the score is 1.

The score of the permutation (2,1) is found as follows.

• Initially, Person 1 has Ball 1, and Person 2 has Ball 2.
  After Snuke's first scream, Person 1 has Ball 2, and Person 2 has Ball 1.
  After Snuke's second scream, Person 1 has Ball 1, and Person 2 has Ball 2.
  Here, every Person i has Ball i, so he stops screaming.
  Thus, the score is 2.

Therefore, the answer in this case is 1^2 + 2^2 = 5.

Sample Input 2

3 3

Sample Output 2

79

All permutations and their scores are listed below.

• (1,2,3): The score is 1.
• (1,3,2): The score is 2.
• (2,1,3): The score is 2.
• (2,3,1): The score is 3.
• (3,1,2): The score is 3.
• (3,2,1): The score is 2.

Thus, we should print 1^3 + 2^3 + 2^3 + 3^3 + 3^3 + 2^3 = 79.

Sample Input 3

50 10000

Sample Output 3

77436607