Problem Statement

Takahashi manages a server monitoring system. The server sends N event logs in chronological order. The event code of the i-th log sent is A_i.

Takahashi checks these logs in the order A_1, A_2, \ldots, A_N and appends them to a record list. However, if the record list is not empty and a log has the same event code as the last element of the record list, it is considered a duplicate and skipped without being added to the list. If the record list is empty, or if the log's event code is different from the last element of the record list, he appends that event code to the end of the record list.

Given the N event codes in chronological order, print the contents of the record list after all logs have been checked.

Constraints

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

Sample Input 1

7
1 1 2 2 2 3 2

Sample Output 1

1
2
3
2

Sample Input 2

6
1 2 1 2 1 2

Sample Output 2

1
2
1
2
1
2

Sample Input 3

15
8 8 8 1 1 2 3 3 2 2 2 5 5 5 1

Sample Output 3

8
1
2
3
2
5
1

Sample Input 4

30
10 10 9 9 8 7 7 7 8 8 8 1000000000 1000000000 1 2 2 3 3 3 2 2 4 4 4 4 5 1 1 6 6

Sample Output 4

10
9
8
7
8
1000000000
1
2
3
2
4
5
1
6

Sample Input 5

1
1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi is in charge of production management at a factory. This factory produces a certain product.

To make 1 unit of the product, exactly 1 of each of M types of parts is required. The initial stock of the j-th part is B_j units.

Today, N orders are processed in the order i = 1, 2, \ldots, N. The i-th order requires delivering exactly A_i units of the product.

When processing the i-th order, if the current stock of every type of part is at least A_i, then A_i units of the product are produced and delivered. In this case, the stock of every type of part decreases by A_i. If even one type of part has stock less than A_i, the order is cancelled — no products are produced and the part stocks do not change.

After all orders have been processed, determine the number of orders that were actually delivered.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq M \leq 5 \times 10^5
• N + M \leq 5 \times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq B_j \leq 10^9
• All input values are integers.

Sample Input 1

4 3
2 1 3 1
5 4 6

Sample Output 1

3

Sample Input 2

5 2
4 2 3 1 2
3 5

Sample Output 2

2

Sample Input 3

8 6
5 7 4 6 3 2 8 1
20 17 23 19 18 21

Sample Output 3

4

Sample Input 4

20 15
8 7 10 6 5 9 4 3 12 2 11 1 13 5 4 7 6 2 8 3
60 55 58 62 57 59 61 56 63 54 64 65 66 53 67

Sample Output 4

9

Sample Input 5

1 1
1000000000
1000000000

Sample Output 5

1

Problem Statement

Along a straight road running east-west, N buildings stand in a row. They are numbered Building 1, Building 2, …, Building N from west to east, and the height of Building i is H_i.

Takahashi is standing at a point further west than Building 1, looking toward the east. Whether a building is visible or not is determined solely by height as follows:

• If the heights of all buildings to the west of Building i (from Building 1 to Building i-1) are strictly less than H_i, then Building i is visible to Takahashi.
• Otherwise, that is, if there exists at least one building among Building 1 to Building i-1 whose height is greater than or equal to H_i, then Building i is blocked by a building in front and is not visible. Note that a building with exactly the same height in front also blocks it.

In particular, Building 1 is always visible since there are no buildings to its west.

Takahashi will choose exactly one building from the N buildings and demolish it. The building to demolish may be either a visible or non-visible building, but this operation must be performed exactly once and cannot be skipped. The demolished building completely disappears, and the view is re-evaluated with the remaining buildings in their original order, treating the demolished building as if it never existed. That is, the demolished building no longer blocks any other buildings, and it is not counted in the number of visible buildings.

Takahashi wants to maximize the number of visible buildings after the demolition by optimally choosing which building to demolish.

Find the maximum number of buildings visible to Takahashi when one building is optimally chosen and demolished.

Constraints

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

Sample Input 1

5
2 1 3 2 4

Sample Output 1

3

Sample Input 2

6
5 3 5 6 6 7

Sample Output 2

4

Sample Input 3

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

Sample Output 3

5

Sample Input 4

30
100 20 50 120 110 130 10 125 140 140 60 150 149 151 5 152 80 153 153 154 1 90 155 154 156 2 157 50 158 159

Sample Output 4

15

Sample Input 5

1
1000000000

Sample Output 5

0

Problem Statement

Takahashi is a project leader managing N employees.

The N employees are numbered employee 1, 2, \ldots, N. Each employee i (1 \leq i \leq N) has an "ability value" P_i. Ability values can be negative.

Takahashi will divide these N employees into at least 1 and at most N groups. Each group consists of employees with consecutive numbers, and every employee belongs to exactly one group. Specifically, we consider a partition where there exists some number of groups k (1 \leq k \leq N) and an integer sequence c_0, c_1, \ldots, c_k satisfying 0 = c_0 < c_1 < \cdots < c_k = N, such that the j-th group (1 \leq j \leq k) consists of employees c_{j-1}+1, c_{j-1}+2, \ldots, c_j. It is allowed to place all N employees into a single group, or to place each employee into their own individual group.

Due to the effect of teamwork, larger groups produce greater synergy. Specifically, the productivity of a group consisting of employees l, l+1, \ldots, r (1 \leq l \leq r \leq N) is calculated by the following formula:

\text{productivity} = (r - l + 1) \times \sum_{i=l}^{r} P_i

Here, (r - l + 1) is the number of people in the group, and \displaystyle\sum_{i=l}^{r} P_i is the sum of ability values within the group. Note that if the sum of ability values within a group is negative, the productivity of that group is also negative.

Takahashi wants to determine the partition that maximizes the total productivity across all groups. Find the maximum value of the total productivity.

Constraints

• 1 \leq N \leq 5000
• -10^6 \leq P_i \leq 10^6 (1 \leq i \leq N)
• All inputs are integers.
• The maximum value of the total productivity fits in a 64-bit signed integer type.

Sample Input 1

3
1 2 3

Sample Output 1

18

Sample Input 2

4
3 -5 -5 3

Sample Output 2

-4

Sample Input 3

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

Sample Output 3

72

Sample Input 4

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

Sample Output 4

555

Sample Input 5

1
-1000000

Sample Output 5

-1000000

Problem Statement

Takahashi is the manager of a printing factory. The factory prints posters of various sizes.

Takahashi has received N orders. The i-th order (1 \leq i \leq N) requires printing C_i posters of the same size, with a width of W_i and a height of H_i.

The factory has M printing machines. The j-th printing machine (1 \leq j \leq M) can only print posters whose width is at least L_j and at most R_j. There is no restriction regarding the height of the poster. That is, regardless of the value of H_i, the j-th printing machine can print posters for the i-th order as long as L_j \leq W_i \leq R_j holds. (Note that although H_i is included in the input as part of the order information, it does not affect the assignment of printing machines.)

Each printing machine can print at most one poster per day. That is, on any single day, at most one poster can be assigned to each printing machine, and a machine cannot print posters for multiple orders on the same day.

It is possible to distribute the C_i posters of a single order among multiple printing machines. Multiple printing machines can print posters for the same order in parallel on the same day, or the printing can span across multiple days. Also, a single printing machine can print posters for different orders on different days.

Find the minimum number of days required to complete all orders. Here, completing all orders means that for each order i (1 \leq i \leq N), all C_i posters have been printed.

If there is an order i for which no printing machine j satisfies L_j \leq W_i \leq R_j, there is no way to print that order, making it impossible to complete all orders. In this case, output -1.

Constraints

• 1 \leq N
• 1 \leq M
• N + M \leq 10^5
• 1 \leq W_i \leq 10^9
• 1 \leq H_i \leq 10^9
• 1 \leq C_i \leq 10^9
• \displaystyle \sum_{i=1}^{N} C_i \leq 10^9
• 1 \leq L_j \leq R_j \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

3

Sample Input 2

2 3
10 100 4
50 200 3
1 20
21 30
60 80

Sample Output 2

-1

Sample Input 3

5 6
5 10 10
12 20 8
20 30 15
30 40 7
40 50 12
1 10
1 25
10 35
15 45
25 50
35 45

Sample Output 3

9

Sample Input 4

12 15
3 100 5
8 200 12
15 150 20
22 300 18
27 120 25
35 80 14
42 90 30
50 110 22
60 130 16
75 160 28
90 170 10
100 180 24
1 20
1 30
5 25
10 40
20 50
25 60
30 70
40 80
45 100
55 95
70 110
80 120
1 100
35 45
90 100

Sample Output 4

15

Sample Input 5

1 1
1000000000 1000000000 1000000000
1 1000000000

Sample Output 5

1000000000