Problem Statement

Takahashi has been assigned to tally the scoring results at a figure skating competition.

There are N contestants in this competition, numbered from 1 to N. Each contestant is evaluated by M judges. Let S_{i,j} denote the score that contestant i (1 \leq i \leq N) received from judge j (1 \leq j \leq M). Each score is an integer between 1 and 100, inclusive.

According to the competition rules, each contestant's final score is calculated by the following procedure:

1. Sort the M scores given by the M judges in ascending order (from smallest to largest).
2. Remove the first score (the minimum) and the last score (the maximum) from the sorted list. Even if there are multiple scores with the same value, only one score is removed from each end.
3. The sum of the remaining M - 2 scores becomes that contestant's final score.

Output the number of the contestant with the highest final score. If there are multiple contestants with the highest final score, output the smallest number among them.

Constraints

• 1 \leq N \leq 10^5
• 3 \leq M \leq 10^5
• N \times M \leq 10^6
• 1 \leq S_{i,j} \leq 100
• All input values are integers.

Sample Input 1

3 3
5 9 3
8 6 7
4 10 1

Sample Output 1

2

Sample Input 2

5 5
50 60 70 80 90
65 75 70 85 55
90 40 80 70 60
100 100 1 1 50
72 68 75 80 71

Sample Output 2

5

Sample Input 3

4 7
80 75 90 60 85 70 95
88 92 78 85 90 83 79
95 91 89 84 87 93 86
100 70 99 88 92 91 85

Sample Output 3

4

Problem Statement

Takahashi found a short-term part-time job listing for N days during summer vacation. Each day has a set reward, and the reward for day i (1 \leq i \leq N) is A_i yen. Some days may have negative rewards, meaning that due to training fees or other self-paid expenses, working on such a day would require him to pay money instead.

Furthermore, for this part-time job, Takahashi must pay 1 yen out of pocket as transportation cost for each day he works. Therefore, the effective profit from working on day i is (A_i - 1) yen.

Due to scheduling constraints, Takahashi can only work on consecutive days. Specifically, he chooses a pair of integers (i, j) satisfying 1 \leq i \leq j \leq N, and works every day consecutively from day i to day j. Note that Takahashi must work at least 1 day (i.e., the case i = j is also allowed).

The total effective profit Takahashi earns is the sum of the effective profits for each day he works:

(A_i - 1) + (A_{i+1} - 1) + \cdots + (A_j - 1) = \left(\sum_{k=i}^{j} A_k\right) - (j - i + 1)

yen. Here, (j - i + 1) corresponds to the number of days worked and represents the total transportation cost for those days.

Find the maximum total effective profit when Takahashi optimally chooses (i, j). Note that the maximum value may be negative, such as when the rewards for all days are small.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

5
3 -1 4 1 2

Sample Output 1

4

Sample Input 2

8
-2 5 3 -4 8 -1 2 -3

Sample Output 2

8

Sample Input 3

15
-1000000000 1000000000 1000000000 -500000000 1000000000 -1 -1 1000000000 500000000 -1000000000 3 2 1 -5 10

Sample Output 3

3999999990

Problem Statement

Takahashi is attempting a mountain trail consisting of N locations. Location 1 is the starting point (foot of the mountain), and location N is the goal (mountain summit).

Each location has an exhaustion level. The exhaustion level of location i is H_i. When Takahashi reaches a location, his stamina decreases by the exhaustion level of that location.

Additionally, M rations are hidden along this trail. The j-th ration is at location P_j, and eating it increases stamina by R_j. There is at most one ration at each location, and each ration can be eaten only once. When Takahashi reaches a location, if there is a ration there, he automatically collects it. He does not need to eat collected rations on the spot and can carry an unlimited number of them.

Takahashi's initial stamina is K. There is no upper limit on stamina, and it can exceed the initial value through recovery.

The trail proceeds according to the following steps. At each location, events occur in the order of Exhaustion \rightarrow Retirement Check \rightarrow Collecting Rations \rightarrow Using Rations. A retirement check means that if stamina is less than 0 at that moment, he retires (fails). Because the stamina increase from using rations occurs after the retirement check, if his stamina is less than 0 immediately after exhaustion, he retires.

1. Initial Setup: Takahashi starts at location 1. His stamina decreases by the exhaustion level H_1 of location 1. If his stamina becomes less than 0, he retires. If he does not retire, he collects the ration at location 1 if there is one, and then can choose to eat any number (possibly 0) of the rations in his possession.
2. Movement: From his current location i, Takahashi moves to either location i+1 or location i+2 (he cannot move to a location beyond location N). If he moves directly to location i+2, he does not visit location i+1, so he does not suffer the exhaustion of location i+1, nor does he obtain the ration at location i+1. His stamina decreases by the exhaustion level of the destination location. If his stamina becomes less than 0, he retires. If he does not retire, he collects the ration at the destination location if there is one, and then can choose to eat any number (possibly 0) of the rations in his possession.
3. Repeat step 2 until reaching location N.

Rations can only be eaten at the timings specified in the steps above (after reaching each location, suffering exhaustion, and passing the retirement check); they cannot be eaten while traveling between locations.

Determine whether Takahashi can reach location N without retiring. If he can, output the maximum possible stamina when he reaches location N and has eaten all remaining rations in his possession, assuming optimal choices of route and timings to eat rations. If he cannot reach location N, output -1.

Constraints

• 2 \leq N \leq 10^6
• 0 \leq M \leq \min(N, 10^5)
• 0 \leq K \leq 10^9
• 0 \leq H_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq P_j \leq N (1 \leq j \leq M)
• 1 \leq R_j \leq 10^9 (1 \leq j \leq M)
• All P_j are distinct.
• All input values are integers.

Sample Input 1

5 2 10
3 4 8 2 5
2 5
4 3

Sample Output 1

4

Sample Input 2

4 0 3
2 5 5 1

Sample Output 2

-1

Sample Input 3

12 5 15
4 7 3 10 2 8 6 1 12 4 5 3
2 10
5 4
7 9
9 20
11 5

Sample Output 3

21

Sample Input 4

30 10 25
5 12 4 20 3 15 7 2 25 6 10 4 18 1 9 14 3 22 5 8 16 2 11 7 30 4 6 13 2 10
3 12
5 8
8 5
10 20
14 6
17 15
20 10
24 25
27 7
29 30

Sample Output 4

75

Sample Input 5

2 2 0
0 0
1 1000000000
2 1000000000

Sample Output 5

2000000000

Problem Statement

Takahashi runs an online shop that sells N products.

Initially, the price of each product i (1 \leq i \leq N) is set to A_i yen. Before starting sales, Takahashi performs Q "price adjustments" in order from the 1-st to the Q-th, following predetermined rules.

For the j-th (1 \leq j \leq Q) price adjustment, a type T_j, a new price X_j, and a cancellation flag R_j are given, and the following steps 1–3 are executed in this order.

1. Selection of target product: Based on the prices of all products at the time the previous price adjustment was completed (or the initial state when j = 1), select one target product.

• If T_j = 1: Select the product with the highest price. If there are multiple products with the highest price, select the one with the smallest product number among them.
• If T_j = 2: Select the product with the lowest price. If there are multiple products with the lowest price, select the one with the smallest product number among them.

1. Price change: Change the price of the product selected in step 1 to X_j yen.

1. Cancellation check: Check the value of the cancellation flag R_j.

• If R_j = 0: The change made in step 2 is finalized as is.
• If R_j = 1: The price change made in step 2 is cancelled, and the price of the selected product is reverted to the value it had before step 2 was executed.

Here, the "completion" of the j-th price adjustment refers to the state after all of steps 1–3 have been executed. If R_j = 1, the price is reverted in step 3, so as a result, the prices of all products do not change before and after the j-th price adjustment. However, note that even when R_j = 1, the selection of the target product in step 1 is still performed.

Find the total price of all products after all price adjustments have been completed.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• T_j \in \{1, 2\} (1 \leq j \leq Q)
• 1 \leq X_j \leq 10^9 (1 \leq j \leq Q)
• R_j \in \{0, 1\} (1 \leq j \leq Q)
• All input values are integers.

Sample Input 1

3 4
10 20 20
1 5 0
2 30 1
2 15 0
1 8 0

Sample Output 1

33

Sample Input 2

4 5
5 5 5 5
2 1 0
1 10 1
1 7 0
2 9 0
2 3 1

Sample Output 2

26

Sample Input 3

8 12
100 50 100 75 25 75 50 25
1 60 0
1 40 1
2 90 0
2 10 0
1 30 0
2 80 1
1 110 0
2 55 0
1 65 1
2 20 0
1 45 0
2 70 0

Sample Output 3

480

Sample Input 4

15 25
1000 500 1500 500 2000 750 1250 1000 250 1750 250 1500 750 2000 1250
1 300 0
2 1800 0
1 600 1
2 400 0
1 2200 0
1 100 0
2 900 1
2 50 0
1 1600 0
2 1400 0
1 700 1
2 2100 0
1 800 0
2 1200 0
1 500 0
2 1900 1
1 1300 0
2 1100 0
1 200 0
2 1700 0
1 1000 1
2 300 0
1 2400 0
2 600 1
1 150 0

Sample Output 4

14250

Sample Input 5

1 1
1000000000
1 1 1

Sample Output 5

1000000000

Problem Statement

Takahashi is looking at N mountains lined up in a row from east to west. Each mountain i (1 \leq i \leq N) has a color C_i and an elevation H_i.

Takahashi calls a pair of mountains of the same color a "matching pair." Since matching pairs harmonize and look photogenic, Takahashi is interested in them.

However, if there is a mountain between mountain i and mountain j (i < j) that is taller than both of them, it blocks the view, making them invisible to each other. Specifically, for a matching pair i and j (i < j), if there exists some k (i < k < j) such that H_k > \max(H_i, H_j), this pair is said to have a "poor view."

Takahashi wants to count the number of matching pairs with a "clear view," meaning pairs where there is no mountain between them that is strictly taller than both.

Find the number of pairs (i, j) (i < j) that satisfy all of the following conditions:

• C_i = C_j
• For all k (i < k < j), H_k \leq \max(H_i, H_j)

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq C_i \leq N
• 1 \leq H_i \leq 10^9
• All H_i are distinct (i.e., if i \neq j, then H_i \neq H_j)
• All input values are integers.

Sample Input 1

5
1 3
2 5
1 4
1 1
2 2

Sample Output 1

2

Sample Input 2

4
1 10
2 20
3 30
4 40

Sample Output 2

0

Sample Input 3

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

Sample Output 3

5

Sample Input 4

30
1 17
2 5
3 28
1 12
4 30
2 9
5 1
3 24
1 20
4 7
5 26
2 14
6 3
1 29
3 11
6 18
4 2
5 22
2 27
7 6
1 15
7 25
3 4
6 21
4 10
5 19
2 8
7 23
6 13
1 16

Sample Output 4

10

Sample Input 5

1
1 1

Sample Output 5

0