Problem Statement

Takahashi is arranging books on a bookshelf. The bookshelf has N shelves: shelf 1, shelf 2, …, shelf N, and each shelf has a width of W centimeters. Initially, all shelves are empty.

There are N books to arrange on the bookshelf, and the i-th book (1 \leq i \leq N) has a thickness of L_i centimeters. It is guaranteed that the thickness of each book is at most W, so every book can individually fit on a single shelf.

When k (k \geq 1) books (with thicknesses a_1, a_2, \ldots, a_k) are lined up from left to right on a shelf, the used width of that shelf is defined as (a_1 + a_2 + \cdots + a_k) + (k - 1) centimeters. This corresponds to always leaving a 1-centimeter gap between adjacent books. For example, the used width of a shelf with only one book equals the thickness of that book, and the used width of a shelf with no books is 0 centimeters.

Takahashi places the books one by one in order from the 1-st book to the N-th book, following the rules below. The "current shelf" is initially shelf 1. When placing the i-th book:

1. If no books are currently placed on the current shelf, place the i-th book starting from the left end of the current shelf. The current shelf does not change.
2. Suppose books are already on the current shelf, and the used width is S centimeters.

• If S + 1 + L_i \leq W, place the i-th book on the current shelf to the right of the already placed books, leaving a 1-centimeter gap. The current shelf does not change.
• If S + 1 + L_i > W, the i-th book does not fit on the current shelf. The shelf after the current shelf (the shelf with the number one greater) becomes the new "current shelf." Since shelves are filled in order from the smallest number, this new shelf is always empty. Place the i-th book starting from the left end of that shelf.

After all N books have been arranged, determine the total number of shelves that have at least one book placed on them.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq W \leq 10^9
• 1 \leq L_i \leq W (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5 10
3 4 2 5 3

Sample Output 1

3

Sample Input 2

8 15
5 5 5 5 5 5 5 5

Sample Output 2

4

Sample Input 3

10 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

10

Problem Statement

Takahashi is working a part-time job analyzing sales data for a chain store.

This chain store has sales records for N days, and the sales on day i (1 \leq i \leq N) were T_i yen.

Takahashi wants to calculate the average sales over every consecutive K-day period and find the maximum value, in order to understand the performance of the period with the best sales.

Specifically, for each integer l (1 \leq l \leq N - K + 1), the average sales over the consecutive K days from day l to day l + K - 1 is defined as

M_l = \frac{T_l + T_{l+1} + \cdots + T_{l+K-1}}{K}

Let M be the maximum value of M_l over all l (1 \leq l \leq N - K + 1).

Find \lfloor M \times 1000 \rfloor, where \lfloor x \rfloor denotes the largest integer not exceeding x (the floor function). This corresponds to truncating M below the 4th decimal place and multiplying by 1000.

Hint: Let S be the maximum sum of sales over any consecutive K days. Since all T_i are integers, S is also an integer, and \lfloor M \times 1000 \rfloor = \left\lfloor \frac{1000 \times S}{K} \right\rfloor holds. Therefore, the answer can be computed using only integer arithmetic.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq T_i \leq 10^6
• All inputs are integers

Sample Input 1

5 3
10 20 30 25 15

Sample Output 1

25000

Sample Input 2

7 2
100 150 80 200 190 50 120

Sample Output 2

195000

Sample Input 3

10 4
1234 5678 9012 3456 7890 2345 6789 1357 2468 8024

Sample Output 3

6509000

Problem Statement

Takahashi has lined up N dominoes in a row. They are numbered 1, 2, \ldots, N from left to right, and each domino i has a positive integer A_i representing its "height."

In this world's domino toppling, a fallen domino collides with the nearest still-standing domino immediately to its right, and if the other domino's height is strictly less than its own, it knocks that domino down as well. Specifically, the chain proceeds according to the following rules:

• When domino i falls, let domino j be the domino that is to the right of i with the smallest number among those that have not yet fallen (i.e., the nearest still-standing domino immediately to the right of domino i).
• If such a domino j exists and A_j < A_i (the height of domino j is strictly less than the height of domino i), then domino i knocks down domino j. Subsequently, the same rule is applied starting from the newly fallen domino j. That is, using domino j's height A_j as the reference, it is determined whether the next still-standing domino to the right can be knocked down.
• If there is no still-standing domino to the right of domino i, or if the height of domino j is greater than or equal to the height of domino i (A_j \geq A_i), the chain stops there.

Takahashi performs the operation of pushing down dominoes with his finger in the order 1, 2, \ldots, N, pushing each one only if it has not yet fallen. If it has already fallen, he does nothing and moves on to the next domino. When he pushes a domino with his finger, the chain rule described above is applied starting from that domino.

After all dominoes have fallen, for each domino i (1 \leq i \leq N), determine the direct cause of domino i falling. If domino i was knocked down by the chain from another domino k (i.e., domino i fell immediately after domino k fell according to the above rules), output that domino's number k. If Takahashi directly pushed it down with his finger, output 0.

Constraints

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

Sample Input 1

5
5 3 4 2 1

Sample Output 1

0 1 0 3 4

Sample Input 2

3
2 2 1

Sample Output 2

0 0 2

Sample Input 3

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

Sample Output 3

0 1 2 0 4 5 0 7 0 9 0 11

Sample Input 4

30
100 90 80 85 70 60 50 75 74 73 20 21 19 18 200 150 160 140 130 120 110 111 109 108 50 49 48 47 46 45

Sample Output 4

0 1 2 0 4 5 6 0 8 9 10 0 12 13 0 15 0 17 18 19 20 0 22 23 24 25 26 27 28 29

Sample Input 5

1
1000000000

Sample Output 5

0

Problem Statement

Takahashi has a grid with N rows and M columns. The cell at row i and column j of the grid contains an integer A_{i,j}.

Takahashi will select one rectangular region from this grid and compute the sum of the values of all cells contained in that region. Here, a "rectangular region" refers to the region consisting of all cells whose row is between r_1 and r_2 (inclusive) and whose column is between c_1 and c_2 (inclusive), where r_1, r_2 (1 \le r_1 \le r_2 \le N) and c_1, c_2 (1 \le c_1 \le c_2 \le M) are chosen integers.

Takahashi wants to choose the rectangular region so that this sum is maximized. Note that a rectangular region must contain at least one cell, so it is not possible to choose no rectangular region and have a sum of 0. In particular, even if all cell values are negative, he must still choose some rectangular region.

Find the maximum possible sum of values within a rectangular region that Takahashi can choose.

Constraints

• 1 \leq N \leq 500
• 1 \leq M \leq 500
• -10^4 \leq A_{i,j} \leq 10^4
• All input values are integers

Sample Input 1

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

Sample Output 1

18

Sample Input 2

2 2
-5 -3
-1 -7

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

14

Sample Input 4

8 10
3 -1 2 -4 5 1 -3 2 4 -2
-2 4 1 3 -1 2 -5 3 1 0
1 -3 5 2 4 -1 3 -2 1 2
-4 2 -1 6 3 5 -2 4 -3 1
0 1 3 -2 4 2 1 -1 5 3
-1 -2 4 1 -3 6 2 3 -4 2
3 1 -5 2 1 -2 4 1 3 -1
-2 3 2 -1 3 1 -3 2 -1 4

Sample Output 4

77

Sample Input 5

1 1
-7

Sample Output 5

-7

Problem Statement

Takahashi is planning to walk a hiking course in a mountainous area.

This course consists of N points arranged in a straight line, and the elevation of point i (1 \leq i \leq N) is H_i. Takahashi starts at point 1 and walks to point N by proceeding through points 1, 2, \ldots, N in order.

Takahashi has a fear of heights, and when moving from point i to point i+1 (1 \leq i \leq N-1), he feels fear if the elevation decreases by K or more (that is, if H_i - H_{i+1} \geq K). He does not feel fear during any other movements.

The course manager can select any number (possibly 0) of points from points 2, 3, \ldots, N-1 and change each of their elevations to any non-negative integer value, so that Takahashi can walk without feeling fear. Different points may be changed to different values, and there is no upper limit on the changed values. However, the elevations of points 1 and N cannot be changed.

Find the minimum number of points whose elevations need to be changed so that Takahashi can walk from point 1 to point N without ever feeling fear. If it is impossible to avoid fear no matter how the elevations are changed, output -1.

Note: Even when N \geq 3, the answer may be -1. If the elevation difference between the unchangeable points 1 and N is too large, fear cannot be avoided no matter how the elevations of intermediate points are changed.

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq K \leq 10^9
• 0 \leq H_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

5 3
10 8 4 5 3

Sample Output 1

1

Sample Input 2

3 5
20 0 5

Sample Output 2

-1

Sample Input 3

12 4
15 13 9 12 8 6 10 5 4 7 3 2

Sample Output 3

4

Sample Input 4

30 7
100 95 90 82 85 78 70 72 65 60 54 58 50 49 42 35 38 31 25 20 23 18 12 10 5 8 3 2 1 0

Sample Output 4

8

Sample Input 5

2 1
0 0

Sample Output 5

0