Problem Statement

At a flea market, the seller Takahashi has lined up N items in order from left to right. The price of the i-th item is A_i yen.

Aoki, a customer, is willing to buy an item as long as it costs at most X yen. For each item, let the character be o if its price is at most X yen and x otherwise, and output the string of length N formed by arranging these characters in order from the leftmost item.

Constraints

• 1 \leq N \leq 100
• 1 \leq X \leq 10000
• 1 \leq A_i \leq 10000
• All input values are integers.

Sample Input 1

5 500
300 800 450 1200 100

Sample Output 1

oxoxo

Sample Input 2

3 100
200 300 400

Sample Output 2

xxx

Sample Input 3

2 9000
1 8999

Sample Output 3

oo

Sample Input 4

1 500
499

Sample Output 4

o

Sample Input 5

5 500
300 1 450 1200 100

Sample Output 5

oooxo

Problem Statement

Takahashi placed N pieces of meat on the grill at a yakiniku restaurant at the same time. The i-th piece of meat will finish cooking A_i seconds after being placed on the grill.

Find which piece of meat finishes cooking first. If multiple pieces finish first, answer the one with the smallest index.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 1000
• All input values are integers.

Sample Input 1

4
30 10 20 40

Sample Output 1

2

Sample Input 2

1
5

Sample Output 2

1

Sample Input 3

3
9 8 7

Sample Output 3

3

Sample Input 4

7
130 623 701 180 63 216 91

Sample Output 4

5

Sample Input 5

8
361 505 856 200 271 262 190 149

Sample Output 5

8

Problem Statement

Takahashi is the chairperson of the school festival organizing committee. The school festival has K categories (such as food & drink, exhibitions, stage performances, etc.), and each category is represented by an integer from 1 to K.

There are N proposed projects in total. The i-th project (1 \leq i \leq N) belongs to category B_i and has an expected visitor count of D_i. Note that there may be categories to which no project belongs.

Takahashi will select and approve some of these N projects (it is also acceptable to approve none). However, at most one project can be approved from each category. In other words, all approved projects must belong to distinct categories.

Under this condition, find the maximum possible total expected visitor count of the approved projects.

Constraints

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

Sample Input 1

5 3
1 10
2 20
1 30
3 15
2 25

Sample Output 1

70

Sample Input 2

4 4
1 100
2 200
3 300
4 400

Sample Output 2

1000

Sample Input 3

10 4
1 50
2 30
3 70
4 10
1 80
2 90
3 60
4 40
1 20
3 100

Sample Output 3

310

Sample Input 4

20 5
1 1000000000
2 999999999
3 500000000
4 750000000
5 100000000
1 999999998
2 1000000000
3 999999997
4 250000000
5 800000000
1 300000000
2 450000000
3 1000000000
4 1000000000
5 999999999
1 600000000
2 700000000
3 850000000
4 600000000
5 500000000

Sample Output 4

4999999999

Sample Input 5

1 1
1 1

Sample Output 5

1

Problem Statement

At Takahashi's workplace, there are two types of daily shifts: Shift A and Shift B.

You are given a string S of length N representing Takahashi's work schedule for the next N days.

The i-th character of S (1 \le i \le N) represents the work schedule for the i-th day, with the following meanings:

• A: Confirmed to work Shift A.
• B: Confirmed to work Shift B.
• C: The shift is undecided.

Takahashi wants to assign either Shift A or Shift B to each day by independently replacing every C in S with either A or B.

At this workplace, working Shift A on two consecutive days is prohibited for health management reasons. Therefore, there must not be two consecutive A's in the string after replacement (that is, the resulting string must not contain AA as a contiguous substring).

Find the number of valid ways to replace the characters, modulo 998244353. If no valid replacement exists, output 0.

Constraints

• 1 \le N \le 2 \times 10^6
• N is an integer.
• S is a string of length N consisting only of A, B, and C.

Sample Input 1

4
ACBC

Sample Output 1

2

Sample Input 2

5
CBAAC

Sample Output 2

0

Sample Input 3

15
CCBACBCBCCABCCC

Sample Output 3

60

Sample Input 4

50
CBCCBCACBCBCACBCBCCBCBCBACBCCBCACBCBCACBCBCCBCBCBA

Sample Output 4

41472

Sample Input 5

1
C

Sample Output 5

2

Problem Statement

Takahashi manages N signboards arranged in a horizontal row. The i-th signboard from the left has an integer A_i written on it.

Takahashi has decided to rewrite the integers on some of the signboards so that the integers written on the signboards are non-decreasing from left to right.

Specifically, letting the integers on the signboards after rewriting be A'_1, A'_2, \dots, A'_N from left to right, he wants to satisfy the following condition for all 1 \le i \le N - 1:

• A'_i \le A'_{i+1}

In one operation, Takahashi can choose one signboard and rewrite the integer written on it to any integer.

Find the minimum number of operations required to satisfy the condition.

Constraints

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

Sample Input 1

5
3 1 4 1 5

Sample Output 1

2

Sample Input 2

4
2 3 3 7

Sample Output 2

0

Sample Input 3

15
10 40 20 50 30 70 60 90 80 100 1000000000 500 800 999999999 1000000000

Sample Output 3

5

Sample Input 4

40
54 12 87 23 91 34 65 18 76 43 99 2 81 59 31 70 45 88 16 62 38 95 27 73 50 84 9 67 41 93 20 78 56 3 89 35 68 47 97 25

Sample Output 4

30

Sample Input 5

1
1000000000

Sample Output 5

0