Problem Statement

You are given a string S. Find the number of strings that can result from performing the following operation exactly once.

• Let N be the length of S. Choose a pair of integers (i,j) such that 1\leq i<j\leq N and swap the i-th and j-th characters of S.

It can be proved that you can always perform it under the constraints of this problem.

Constraints

• S is a string of length between 2 and 10^6, inclusive, consisting of lowercase English letters.

Sample Input 1

abc

Sample Output 1

3

The length of S is 3, so 1\leq i<j\leq 3 is satisfied by three pairs of integers (i,j): (1,2), (1,3), and (2,3).

• Swapping the 1-st and 2-nd characters of S results in S being bac.
• Swapping the 1-st and 3-rd characters of S results in S being cba.
• Swapping the 2-nd and 3-rd characters of S results in S being acb.

Therefore, the operation on abc results in one of the three strings: bac, cba, and acb, so print 3.

Sample Input 2

aaaaa

Sample Output 2

1

Swapping any two characters results in S remaining aaaaa. Thus, only one string can result from the operation.

Problem Statement

There are N types of beans, one bean of each type. The i-th type of bean has a deliciousness of A_i and a color of C_i. The beans are mixed and can only be distinguished by color.

You will choose one color of beans and eat one bean of that color. By selecting the optimal color, maximize the minimum possible deliciousness of the bean you eat.

Constraints

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

Sample Input 1

4
100 1
20 5
30 5
40 1

Sample Output 1

40

Note that beans of the same color cannot be distinguished from each other.

You can choose color 1 or color 5.

• There are two types of beans of color 1, with deliciousness of 100 and 40. Thus, the minimum deliciousness when choosing color 1 is 40.
• There are two types of beans of color 5, with deliciousness of 20 and 30. Thus, the minimum deliciousness when choosing color 5 is 20.

To maximize the minimum deliciousness, you should choose color 1, so print the minimum deliciousness in that case: 40.

Sample Input 2

10
68 3
17 2
99 2
92 4
82 4
10 3
100 2
78 1
3 1
35 4

Sample Output 2

35

Problem Statement

You are given a permutation P = (P_1, P_2, \dots, P_N) of (1, 2, \dots, N).

A length-K sequence of indices (i_1, i_2, \dots, i_K) is called a good index sequence if it satisfies both of the following conditions:

• 1 \leq i_1 < i_2 < \dots < i_K \leq N.
• The subsequence (P_{i_1}, P_{i_2}, \dots, P_{i_K}) can be obtained by rearranging some consecutive K integers.
  Formally, there exists an integer a such that \lbrace P_{i_1},P_{i_2},\dots,P_{i_K} \rbrace = \lbrace a,a+1,\dots,a+K-1 \rbrace.

Find the minimum value of i_K - i_1 among all good index sequences. It can be shown that at least one good index sequence exists under the constraints of this problem.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq N
• P_i \neq P_j if i \neq j.
• All input values are integers.

Sample Input 1

4 2
2 3 1 4

Sample Output 1

1

The good index sequences are (1,2),(1,3),(2,4). For example, (i_1, i_2) = (1,3) is a good index sequence because 1 \leq i_1 < i_2 \leq N and (P_{i_1}, P_{i_2}) = (2,1) is a rearrangement of two consecutive integers 1, 2.

Among these good index sequences, the smallest value of i_K - i_1 is for (1,2), which is 2-1=1.

Sample Input 2

4 1
2 3 1 4

Sample Output 2

0

i_K - i_1 = i_1 - i_1 = 0 in all good index sequences.

Sample Input 3

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

Sample Output 3

5

Problem Statement

In AtCoder Kingdom, N kinds of takoyakis (ball-shaped Japanese food) are sold. A takoyaki of the i-th kind is sold for A_i yen.

Takahashi will buy at least one takoyaki in total. He is allowed to buy multiple takoyakis of the same kind.

Find the K-th lowest price that Takahashi may pay. Here, if there are multiple sets of takoyakis that cost the same price, the price is counted only once.

Constraints

• 1 \le N \le 10
• 1 \le K \le 2 \times 10^5
• 1 \le A_i \le 10^9
• All values in the input are integers.

Sample Input 1

4 6
20 25 30 100

Sample Output 1

50

The four kinds of takoyakis sold in AtCoder Kingdom cost 20 yen, 25 yen, 30 yen, and 100 yen.

The six lowest prices that Takahashi may pay are 20 yen, 25 yen, 30 yen, 40 yen, 45 yen, and 50 yen. Thus, the answer is 50.

Note that at least one takoyaki must be bought.

Sample Input 2

2 10
2 1

Sample Output 2

10

Note that a price is not counted more than once even if there are multiple sets of takoyakis costing that price.

Sample Input 3

10 200000
955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872

Sample Output 3

5705443819

Problem Statement

Given is a sequence A of length N. You can do this operation any number of times: when the length of the sequence is at least 2, choose two adjacent values, delete them, and insert their sum where they were. How many sequences can result from zero or more operations? Find the count modulo 998244353.

Constraints

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

Sample Input 1

3
1 -1 1

Sample Output 1

4

The following four sequences can result from zero or more operations.

• {1,-1,1}
• {1,0}
• {0,1}
• {1}

Sample Input 2

10
377914575 -275478149 0 -444175904 719654053 -254224494 -123690081 377914575 -254224494 -21253655

Sample Output 2

321