Problem Statement

Takahashi is keeping observation records of wild flowers. During today's walk, he found N flowers and took a photo of each one.

Each flower is assigned a species number from 1 to 100. To create an encyclopedia, Takahashi decided that if multiple flowers of the same species are found, only one photo will be included in the encyclopedia. In other words, the encyclopedia contains at most one photo per species.

Given the species numbers of each flower in the order they were found, determine the number of photos to be included in the encyclopedia (i.e., the number of distinct species among the found flowers) and the sum of all species numbers included in the encyclopedia.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq S_i \leq 100
• All inputs are integers

Sample Input 1

5
3 1 4 1 5

Sample Output 1

4 13

Sample Input 2

10
7 2 7 3 2 8 3 7 1 4

Sample Output 2

6 25

Sample Input 3

20
50 25 75 25 100 50 30 75 25 100 1 30 50 99 1 75 42 99 42 88

Sample Output 3

9 510

Problem Statement

Takahashi is a mail carrier. In his delivery area, there are N points arranged in a straight line, including the post office, numbered 1, 2, \ldots, N in order. The distance between any two adjacent points is 1. Point 1 contains the post office.

For each point i (2 \leq i \leq N), B_i letters must be delivered. No letters need to be delivered to point 1 (the post office).

To deliver the letters, Takahashi can perform the following delivery route 0 or more times, as many times as he likes:

1. Departure: Start at the post office (point 1). Upon departure, choose any number of undelivered letters to carry. He may choose to carry none. There is no limit to the number of letters he can carry in a single route.
2. Outbound Journey: Move 1 point at a time from point 1 in the direction of increasing point numbers (point 1 \to 2 \to 3 \to \cdots). At each point reached during the outbound journey, he can deliver any number of letters currently in his possession that are addressed to that point (he may also choose not to deliver any). Letters can only be delivered to their designated destination point, not to any other points. He can end the outbound journey and transition to the return journey at any point he has reached (he can even transition to the return journey immediately at point 1, in which case no movement occurs and the fatigue incurred is 0).
3. Return Journey: Return directly to the post office (point 1) from the point where the outbound journey ended. No fatigue is incurred during the return journey. Additionally, no letters can be delivered during the return journey. Undelivered letters are brought back to the post office and can be carried again in subsequent routes.

Letters addressed to the same point can be delivered across multiple different routes.

The fatigue incurred in a single route is calculated as follows: When moving from point p to the adjacent point p+1 (p \geq 1) during the outbound journey, fatigue equal to the number of letters currently in his possession (the number of carried letters that have not yet been delivered to any point and remain in his hands) is incurred. For example, even during the movement from point 1 to point 2 upon departure, fatigue equal to the number of letters in his possession is incurred. Fatigue is only incurred during outbound movements. The fatigue of a single route is the sum of the fatigue incurred during all movements in that route's outbound journey.

Find the minimum sum of fatigue across all routes required to deliver all letters.

Constraints

• 2 \leq N \leq 10^6
• 0 \leq B_i \leq 10^7 (2 \leq i \leq N)
• All input values are integers.
• Under these constraints, the answer fits within a signed 64-bit integer.

Sample Input 1

4
2 1 3

Sample Output 1

13

Sample Input 2

5
0 4 0 2

Sample Output 2

16

Sample Input 3

12
5 0 8 3 12 1 0 7 4 10 6

Sample Output 3

365

Sample Input 4

30
100 250 0 75 320 18 999 40 0 560 123 456 789 10 2048 37 81 600 5 900 333 0 712 64 128 1024 16 450 777

Sample Output 4

184621

Sample Input 5

2
10000000

Sample Output 5

10000000

Problem Statement

Takahashi processes N tasks in order using his laptop. The tasks must be executed sequentially from the 1-st task to the N-th task.

To complete the i-th task, a processing power of at least H_i is required.

Takahashi's laptop has an initial battery level of M. For each task, he chooses and executes it in one of the following two modes:

• Power Saving Mode: Exerts a processing power of A for the task. The battery level does not change.
• Full Power Mode: Let p be the current battery level. Exerts a processing power of p for the task. However, using Full Power Mode consumes a large amount of battery, and the battery level after use becomes \lfloor p / 2 \rfloor (where \lfloor x \rfloor denotes the greatest integer less than or equal to x).

For each task, the mode selection is made exactly once. If the exerted processing power is greater than or equal to the required processing power for that task, the task can be completed.

Determine whether Takahashi can complete all N tasks. If he can, find the minimum number of times he needs to use Full Power Mode.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq M \leq 10^{18}
• 1 \leq A \leq 10^{18}
• 1 \leq H_i \leq 10^{18}
• All input values are integers.

Sample Input 1

5 20 5
3 10 4 8 5

Sample Output 1

2

Sample Input 2

4 10 3
2 9 6 4

Sample Output 2

-1

Sample Input 3

15 1000 50
10 60 45 500 50 200 30 90 49 60 20 50 1 40 45

Sample Output 3

5

Sample Input 4

50 1000000000000 1000
500 1000000000000 999 400000000000 1000 200000000000 700 100000000000 1000 60000000000 800 30000000000 200 15000000000 900 7000000000 999 3000000000 123 1500000000 1000 900000000 50 400000000 888 200000000 777 100000000 666 50000000 555 25000000 444 12000000 333 6000000 222 3000000 111 1500000 1000 700000 950 350000 900 200000 800 100000 700 50000

Sample Output 4

25

Sample Input 5

1 1000000000000000000 1
1000000000000000000

Sample Output 5

1

Problem Statement

Takahashi is the manager of a distribution center. This distribution center has N trucks, and he wants to load and deliver as many packages as possible out of the M packages that arrived today.

The weight of package j (1 \leq j \leq M) is D_j.

For truck i (1 \leq i \leq N), a weight limit per package E_i and a maximum number of packages C_i are specified. Truck i can only load packages whose weight is at most E_i (i.e., packages j satisfying D_j \leq E_i), and the number of packages it can carry is at most C_i. The weight condition is checked individually for each package. That is, even when loading multiple packages onto a single truck, it is sufficient that each individual package's weight is at most E_i; there is no constraint on the total weight of the loaded packages.

Each package, if loaded onto a truck, must be loaded onto exactly one truck. The same package cannot be loaded onto multiple trucks. Also, it is not necessary to deliver all packages; some packages may remain unloaded on any truck.

Find the maximum number of packages that can be delivered.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq E_i \leq 10^9
• 1 \leq C_i \leq M
• 1 \leq D_j \leq 10^9
• All input values are integers.

Sample Input 1

3 5
5 2
10 1
3 2
2 4 6 8 11

Sample Output 1

3

Sample Input 2

2 4
3 2
5 2
6 7 8 9

Sample Output 2

0

Sample Input 3

7 15
4 3
8 2
15 4
10 1
6 5
20 2
12 3
1 5 6 7 8 9 10 11 12 13 14 15 16 20 21

Sample Output 3

14

Sample Input 4

20 60
100 3
50 4
200 5
75 2
150 6
30 5
500 4
250 3
10 10
90 2
120 4
60 6
300 5
40 3
180 7
220 2
15 8
80 4
1000 6
130 3
5 12 18 25 33 37 42 48 55 59 63 70 77 83 88 92 99 105 111 119 125 132 140 148 155 163 172 181 190 205 215 230 245 260 275 290 310 330 350 370 390 410 430 450 470 490 510 530 550 570 590 610 700 800 900 1000 1100 1200 1300 1400

Sample Output 4

46

Sample Input 5

1 1
1000000000 1
1000000000

Sample Output 5

1

Problem Statement

Takahashi works as a librarian at a library. The library has N shelves arranged in a horizontal row, numbered 1, 2, \ldots, N from left to right.

Initially, the number of books on each shelf is 0. Takahashi will perform Q operations in order. Each operation is one of the following three types:

• Operation 1: Given integers l, r. Add 1 book to each of shelves l, l+1, \ldots, r. That is, the number of books on each shelf in this range increases by 1.
• Operation 2: Given an integer p. Remove all books from shelf p, setting the number of books on shelf p to 0. (If the number of books is already 0, nothing happens.)
• Operation 3: Given integers l, r. Find the total number of books currently placed on shelves l, l+1, \ldots, r.

For each Operation 3, output the answer.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• For Operations 1 and 3, 1 \leq l \leq r \leq N
• For Operation 2, 1 \leq p \leq N
• There is at least one Operation 3
• All input values are integers
• It is guaranteed that the answer at the time of each Operation 3 is between 0 and 2^{63} - 1, inclusive (i.e., it fits in a signed 64-bit integer)

Sample Input 1

5 7
3 1 5
1 2 4
3 1 5
1 3 5
2 3
3 2 4
3 5 5

Sample Output 1

0
3
3
1

Sample Input 2

3 8
2 2
3 1 3
1 1 1
1 1 3
3 1 1
2 1
3 1 2
3 3 3

Sample Output 2

0
2
1
1

Sample Input 3

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

Sample Output 3

15
4
13
7
17
10

Sample Input 4

30 30
1 1 30
1 1 15
1 16 30
3 1 30
2 1
2 30
3 1 5
1 5 25
3 20 30
2 10
2 20
1 10 20
3 10 20
1 1 1
1 30 30
3 1 30
2 15
1 14 16
3 14 16
1 2 29
2 16
3 15 17
1 1 30
3 1 1
2 1
3 1 30
1 7 7
2 7
3 7 7
3 28 30

Sample Output 4

60
8
26
38
84
11
7
2
133
0
10

Sample Input 5

1 7
3 1 1
2 1
1 1 1
1 1 1
3 1 1
2 1
3 1 1

Sample Output 5

0
2
0