Problem Statement

Takahashi is standing at the entrance of a hiking course. In front of him, he can see N mountains lined up in a row from front to back. The elevation of the i-th mountain from the front (1 \leq i \leq N) is H_i meters.

In this problem, we consider the visibility of mountains using the following simple model. Whether a mountain is visible or not is determined solely by the relative heights of that mountain and the mountains in front of it. The distances between mountains are not considered.

Specifically, the i-th mountain from the front is visible if and only if the following condition is satisfied:

• For every integer j satisfying 1 \leq j < i, H_j < H_i holds.

In other words, if there exists even one mountain among the mountains in front (from the 1-st to the (i-1)-th) whose elevation is H_i or greater, then the i-th mountain is hidden behind a mountain in front and is not visible. Note that a mountain is also not visible if there is a mountain in front with exactly the same elevation.

The frontmost mountain (the 1-st mountain) is always visible since there are no mountains in front of it.

Find all the numbers (integers from 1 to N) of the mountains visible to Takahashi.

Constraints

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

Sample Input 1

5
3 1 4 1 5

Sample Output 1

1 3 5

Sample Input 2

8
10 20 15 25 5 30 28 35

Sample Output 2

1 2 4 6 8

Sample Input 3

15
100 50 80 120 110 130 125 140 200 150 180 250 240 300 299

Sample Output 3

1 4 6 8 9 12 14

Problem Statement

Takahashi has returned from a trip. He purchased N souvenirs at his destination, but since his suitcase can hold at most N - K items, he must give up K souvenirs.

Each of the N souvenirs is numbered from 1 to N, and souvenir i (1 \leq i \leq N) has a satisfaction value D_i. The satisfaction value represents the happiness gained from bringing that souvenir home.

Takahashi will choose K distinct souvenirs from the N souvenirs to give up, and bring home all of the remaining N - K souvenirs. He wants to optimally choose which souvenirs to give up so as to maximize the total satisfaction value of the souvenirs he brings home.

Find the maximum possible total satisfaction value of the souvenirs he brings home.

Constraints

• 1 \leq K < N \leq 2 \times 10^5
• 1 \leq D_i \leq 10^9
• All inputs are integers

Sample Input 1

5 2
3 1 4 1 5

Sample Output 1

12

Sample Input 2

8 3
10 20 30 40 50 60 70 80

Sample Output 2

300

Sample Input 3

15 6
1000000000 1 999999999 2 888888888 3 777777777 4 666666666 5 555555555 6 444444444 7 333333333

Sample Output 3

5666666669

Problem Statement

Takahashi is a teacher at a crafting class. In today's lesson, he plans to teach the students a craft using rope.

There are N students in the classroom, and Takahashi has one rope of length L. He wants to cut this rope into pieces and distribute them to the students so that as many students as possible can participate in the craft.

The following rules apply to cutting and distributing the rope:

• The number of cuts made to the rope is between 0 and K, inclusive. By choosing k (0 \leq k \leq K) positions on a single rope and cutting it, the rope is divided into exactly k + 1 pieces. The length of each piece may be any positive real number (that is, any real number greater than 0).
• Each piece can be given to at most one student. It is allowed for some pieces not to be given to any student.
• Each student can receive at most one piece. It is allowed for some students not to receive any piece.
• The i-th student (1 \leq i \leq N) can participate in the craft if and only if they receive a piece of length at least A_i.

When Takahashi optimally chooses how to cut the rope and how to distribute the pieces to the students, find the maximum number of students who can participate in the craft.

Constraints

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

Sample Input 1

4 10 2
3 2 4 5

Sample Output 1

3

Sample Input 2

5 15 3
5 3 4 6 2

Sample Output 2

4

Sample Input 3

8 1000000000 5
100000000 200000000 150000000 300000000 50000000 250000000 400000000 100000000

Sample Output 3

6

Problem Statement

Takahashi is the coach of a sports club with N players. The players are numbered from 1 to N, and players with different numbers are considered distinct. The skill value of player i (1 \leq i \leq N) is an integer W_i.

Takahashi is going to form a team from the N players. For each player, he decides exactly once whether to "select" or "not select" them (the same player cannot be selected multiple times). Including the case where no one is selected, there are 2^N possible ways to form a team.

Let \lfloor x \rfloor denote the largest integer not exceeding x. Among the 2^N possible selections, those where the number of selected players is at least \lfloor N/2 \rfloor + 1 are called valid selections. For example, when N = 5, at least 3 players must be selected, and when N = 6, at least 4 players must be selected.

For each valid selection, the score is defined as the sum of the skill values of the selected players. For all valid selections, compute each score and find the total sum of all these scores. If different selections have the same score, each is counted separately in the sum.

Since the answer can be very large, output the remainder when divided by 998244353.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq W_i \leq 10^9
• All inputs are integers.

Sample Input 1

3
1 2 3

Sample Output 1

18

Sample Input 2

4
1 2 3 4

Sample Output 2

40

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10

Sample Output 3

14080

Sample Input 4

20
15 92 65 35 89 79 32 38 46 26 43 38 32 79 50 28 84 19 71 69

Sample Output 4

270008320

Sample Input 5

1
1000000000

Sample Output 5

1755647

Problem Statement

Takahashi is the manager of an industrial park consisting of N lots. Each lot is numbered from 1 to N, and a warehouse capable of storing up to P_i tons of goods can be built on lot i.

One day, a request was made to store a total of M tons of goods in the industrial park. Takahashi wants to store as many goods as possible while satisfying the conditions described below.

The industrial park has K corridors, where the i-th corridor directly connects lot U_i and lot V_i. Building warehouses simultaneously on two lots that are directly connected by a corridor is prohibited, as the routes of delivery trucks would interfere with each other. If two lots are not directly connected by a corridor, warehouses may be built on both of them simultaneously without any issues.

Specifically, Takahashi stores goods according to the following procedure:

1. Choose a set S of lots on which to build warehouses (S may be empty). No two lots in S may be directly connected by a corridor.
2. For each lot i in S, assign an integer amount of goods between 0 and P_i inclusive. Lots not in S have no warehouse, so their goods amount is 0.
3. The total amount of goods across all lots must be at most M.

Find the maximum possible value of the total amount of goods across all lots.

Constraints

• 1 \leq N \leq 40
• 1 \leq M \leq 10^{15}
• 0 \leq K \leq \frac{N(N-1)}{2}
• 1 \leq P_i \leq 10^{12} (1 \leq i \leq N)
• 1 \leq U_i < V_i \leq N (1 \leq i \leq K)
• (U_i, V_i) \neq (U_j, V_j) (i \neq j)
• All input values are integers

Sample Input 1

4 10 2
3 5 4 6
1 2
3 4

Sample Output 1

10

Sample Input 2

6 100 5
10 20 30 15 25 5
1 2
2 3
3 4
4 5
5 6

Sample Output 2

65

Sample Input 3

10 1500000000000 8
100000000000 200000000000 150000000000 300000000000 250000000000 50000000000 400000000000 180000000000 350000000000 120000000000
1 2
2 3
1 5
4 7
4 9
5 6
7 9
8 9

Sample Output 3

1150000000000