Problem Statement

Takahashi has been asked by his school teacher to compile the grading results of a test.

For this test, a reference score of S points and a tolerance of T points are set. If the absolute difference between a student's score A_i and the reference score S is at most T, that is, if |A_i - S| \leq T, then the student is judged as "passing."

N students took the test, and the score of the i-th student (1 \leq i \leq N) was A_i points.

Find the number of students who passed.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq S \leq 100
• 0 \leq T \leq 100
• 0 \leq A_i \leq 100 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

5 60 10
55 70 62 45 58

Sample Output 1

4

Sample Input 2

8 75 5
80 75 70 68 82 74 76 90

Sample Output 2

5

Sample Input 3

15 50 0
50 49 51 50 48 52 50 50 47 53 50 46 54 50 55

Sample Output 3

6

Problem Statement

Takahashi is a school teacher in charge of selecting the class representative. There are N students in the class, and each student is assigned an attendance number from 1 to N. The leadership score of student i is A_i.

Currently, the student with attendance number 1 is provisionally registered as the class representative. Takahashi will change the representative if there exists a student other than the current representative whose leadership score is strictly greater than that of the current representative.

Specifically, Takahashi follows the rules below:

1. If there exists one or more students whose leadership score is strictly greater than that of the current representative (the student with attendance number 1), the student with the highest leadership score among them is appointed as the new representative. If there are multiple students with the highest leadership score, the one with the smallest attendance number is chosen.
2. If there is no student whose leadership score is strictly greater than that of the current representative, the representative is not changed.

If Takahashi changed the representative, output the attendance number of the new representative. If no change was made, output -1.

Constraints

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

Sample Input 1

5
3 7 5 7 2

Sample Output 1

2

Sample Input 2

4
10 5 8 3

Sample Output 2

-1

Sample Input 3

10
50 120 80 120 90 150 150 30 100 75

Sample Output 3

6

Problem Statement

Takahashi is trying to build a wireless network using N base stations. The base stations are numbered from 1 to N. The base stations are placed on a number line, and base station i is located at coordinate X_i. No two base stations are placed at the same coordinate.

Each base station is equipped with a wireless device that has the same communication range K, where K is a non-negative integer. Two base stations i and j can communicate directly if the distance between them is at most K, that is, |X_i - X_j| \leq K.

Takahashi wants to build a network such that any two distinct base stations can communicate, either directly or by relaying through one or more other base stations. More precisely, for any two distinct base stations s and t, there should exist a sequence of base stations s = v_1, v_2, \ldots, v_m = t (m \geq 2) such that consecutive stations v_k and v_{k+1} (1 \leq k \leq m-1) can each communicate directly. Note that when N = 1, there is only one base station, so this condition is always satisfied regardless of the value of K.

To reduce the cost of the wireless devices, Takahashi wants to make the communication range K as small as possible.

Since all base station coordinates are integers, the minimum value of K that satisfies the condition is guaranteed to be a non-negative integer. Find this minimum value.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq X_i \leq 10^9
• X_i \neq X_j (i \neq j)
• All input values are integers

Sample Input 1

3
1 5 3

Sample Output 1

2

Sample Input 2

5
10 25 15 40 30

Sample Output 2

10

Sample Input 3

8
100 350 200 550 700 900 450 1000

Sample Output 3

200

Problem Statement

Takahashi is in charge of shift management as the store manager at his part-time workplace.

He needs to create a shift schedule for the upcoming N business days. Each business day is numbered 1, 2, \ldots, N, and business day i (1 \leq i \leq N) has a required skill level H_i and an expected sales amount S_i.

Takahashi's store has M part-time workers, and each worker j (1 \leq j \leq M) has a skill level P_j. To assign worker j to business day i, the condition H_i \leq P_j must be satisfied. In other words, only workers whose skill level is at least the required skill level for that day can be assigned to it.

Takahashi wants to assign all M part-time workers to distinct business days. Since M \leq N, there may be business days with no worker assigned. Specifically, the assignment must satisfy all of the following conditions:

• Each worker is assigned to exactly 1 business day. That is, all M workers are assigned to some business day, and no one is left unassigned.
• At most 1 worker is assigned to each business day. That is, no business day has 2 or more workers assigned to it.
• If worker j is assigned to business day i, then H_i \leq P_j must hold.

The expected sales are obtained only for business days that have a worker assigned. That is, if the set of business days with assigned workers in a certain assignment is T, then the total sales for that assignment is \displaystyle\sum_{i \in T} S_i.

Determine whether it is possible to assign all workers in a way that satisfies the above conditions. If it is possible, find the maximum total sales among all valid assignments. If it is impossible, output -1.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• 1 \leq H_i \leq 10^9
• 1 \leq S_i \leq 10^9
• 1 \leq P_j \leq 10^9
• All inputs are integers
• The values of H_i, S_i, P_j may coincide, both among variables of the same type and among variables of different types

Sample Input 1

5 3
3 100
5 200
2 150
4 80
1 50
4 3 2

Sample Output 1

330

Sample Input 2

4 3
5 100
5 200
5 300
5 400
3 4 2

Sample Output 2

-1

Sample Input 3

8 5
10 500
7 300
15 800
5 200
12 600
3 100
8 450
20 1000
8 12 5 15 10

Sample Output 3

2550

Problem Statement

Takahashi has a sequence of N integers A_1, A_2, \ldots, A_N.

Takahashi wants to select one contiguous interval from this sequence. Specifically, he chooses a pair of integers (l, r) (1 \leq l \leq r \leq N) and extracts the elements from the l-th to the r-th.

The score of the chosen interval is defined as follows:

f(l, r) = \sum_{i=l}^{r} A_i + (r - l + 1) \times M

That is, the score is the sum of the elements in the interval plus the product of the interval length (r - l + 1) and a positive integer M.

Find the number of integer pairs (l, r) (1 \leq l \leq r \leq N) such that the score is at most K.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^9
• 1 \leq K \leq 10^{18}
• -10^9 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers.

Sample Input 1

5 2 10
1 3 2 4 1

Sample Output 1

9

Sample Input 2

7 3 20
-2 5 -1 4 3 -3 2

Sample Output 2

22

Sample Input 3

10 1000000000 5000000000
100 -500 300 200 -100 400 -200 150 250 -50

Sample Output 3

35