Problem Statement

Takahashi is a member of the kendo club, and today he needs to choose an opponent for a practice match.

There are N members in the kendo club other than Takahashi, and each member has a skill value assigned to them. The members are numbered from 1 to N, and the skill value of member i (1 \leq i \leq N) is D_i.

Takahashi's current skill value is L. The condition for Takahashi to win a practice match against member i is that L \geq D_i holds. In other words, he can win if his skill value is greater than or equal to the opponent's skill value.

The coach will recommend the "best practice partner for growth" to Takahashi. According to the coach's policy, practicing against the member who Takahashi can beat but whose skill is as close to his own as possible — that is, the member with the highest skill value among those he can beat — is expected to yield the maximum growth.

Specifically, among the members satisfying L \geq D_i, the member with the maximum D_i is recommended. If there are multiple such members, the one with the smallest member number is chosen.

Find the number of the member recommended by the coach.

However, if there is no member that Takahashi can beat, output -1.

Constraints

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

Sample Input 1

5 10
3 14 10 7 10

Sample Output 1

3

Sample Input 2

3 5
8 12 6

Sample Output 2

-1

Sample Input 3

10 50
45 60 50 30 50 70 48 55 49 50

Sample Output 3

3

Sample Input 4

20 1000000000
999999999 1000000000 999999998 500000000 1000000000 999999997 800000000 1000000000 999999999 600000000 700000000 900000000 1000000000 999999996 850000000 1000000000 750000000 950000000 999999999 1000000000

Sample Output 4

2

Sample Input 5

1 1
1

Sample Output 5

1

Problem Statement

Takahashi is in charge of managing N lockers in the school gymnasium. The lockers are numbered from 1 to N. Initially, all lockers are closed.

Takahashi will perform N operations. In the i-th operation (i = 1, 2, \ldots, N), for every locker whose number is a multiple of i (including locker number i itself), he toggles its state: if it is open, he closes it, and if it is closed, he opens it.

For example, in the 1st operation, he toggles the state of all lockers whose numbers are multiples of 1, namely lockers 1, 2, \ldots, N. In the 2nd operation, he toggles the state of lockers whose numbers are multiples of 2 and at most N, namely lockers 2, 4, 6, \ldots. In the 3rd operation, he toggles the state of lockers whose numbers are multiples of 3 and at most N, namely lockers 3, 6, 9, \ldots.

After all operations are completed, find the number of lockers that are open.

Constraints

• 1 \leq N \leq 10^{18}
• N is an integer

Sample Input 1

10

Sample Output 1

3

Sample Input 2

100

Sample Output 2

10

Sample Input 3

1000000000000000000

Sample Output 3

1000000000

Problem Statement

Takahashi is in charge of arranging N seats lined up in a row at a cultural festival venue. The seats are numbered 1 through N from left to right.

Currently, some seats are already occupied by guests. Specifically, seat i is occupied if S_i = 1, and vacant if S_i = 0.

Takahashi can select 0 or more vacant seats as he likes and guide one new guest to each selected seat. However, he cannot move or remove guests who are already seated. Also, each seat can hold at most 1 person. Furthermore, due to the venue's ventilation rules, the following condition must be satisfied:

• After all guests have been guided to their seats, there must be no three consecutive seats that are all occupied.

In other words, if we denote the state of seat i after all guidance is complete as T_i (1 if occupied, 0 if vacant), then for every i satisfying 1 \leq i \leq N-2, it must not be the case that T_i = T_{i+1} = T_{i+2} = 1. It is guaranteed in the input that the initial state already satisfies this condition.

Takahashi wants to guide as many new guests as possible while satisfying this condition. Find the maximum number of new guests that can be guided.

Constraints

• 1 \leq N \leq 2 \times 10^5
• S_i \in \{0, 1\} (1 \leq i \leq N)
• In the initial state given in the input, there are no three consecutive seats that are all occupied. That is, there is no i (1 \leq i \leq N-2) such that S_i = S_{i+1} = S_{i+2} = 1.
• All input values are integers.

Sample Input 1

5
0 0 1 0 0

Sample Output 1

2

Sample Input 2

7
1 0 0 0 0 0 1

Sample Output 2

3

Sample Input 3

15
0 0 0 1 0 0 0 0 1 1 0 0 0 0 0

Sample Output 3

7

Sample Input 4

30
0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0

Sample Output 4

12

Sample Input 5

1
0

Sample Output 5

1

Problem Statement

Takahashi is the manager of a delivery center. The delivery center has N packages to deliver, and each package has a "preferred delivery date" specified by its recipient. The preferred delivery date of the i-th package is day D_i.

The delivery center can operate for exactly K consecutive days. Specifically, Takahashi chooses any integer s and sets the operation period to be the K days from day s to day s + K - 1 (inclusive).

Takahashi must deliver all packages within this operation period. If the delivery date of the i-th package is x_i, then x_i must be an integer satisfying s \leq x_i \leq s + K - 1. There is no upper limit on the number of packages that can be delivered in a single day, and multiple packages can be delivered on the same day.

If the i-th package is delivered on day x_i, the dissatisfaction for that package is |D_i - x_i|. If the package is delivered exactly on the preferred delivery date, the dissatisfaction is 0, but the further the delivery date is from the preferred date, the greater the dissatisfaction.

Takahashi wants to choose the starting day s of the operation period appropriately, and also decide the delivery date of each package within the operation period appropriately, in order to minimize the total dissatisfaction of all packages \displaystyle \sum_{i=1}^{N} |D_i - x_i|. Find this minimum value.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^9
• 1 \leq D_i \leq 10^9
• All inputs are integers

Sample Input 1

5 3
1 2 3 4 5

Sample Output 1

2

Sample Input 2

4 10
5 8 12 20

Sample Output 2

6

Sample Input 3

7 5
100 102 105 110 115 118 120

Sample Output 3

34

Problem Statement

Takahashi is taking a walk on a one-dimensional number line. Initially, Takahashi is at coordinate 0.

Takahashi has N movement plans. Executing the i-th (1 \leq i \leq N) plan adds D_i to his current coordinate. D_i is a non-zero integer; when positive, he moves in the positive direction, and when negative, he moves in the negative direction.

There are M barricades placed on the number line. The j-th (1 \leq j \leq M) barricade is at coordinate X_j. When executing a plan moves Takahashi from his current coordinate s to coordinate s + D_i, if there exists at least one barricade between s and s + D_i (inclusive of both endpoints), that is, if there exists an X_j satisfying \min(s,\, s + D_i) \le X_j \le \max(s,\, s + D_i), then a collision occurs and the plan cannot be executed.

Takahashi considers the plans in order from the 1-st to the N-th. For each plan, if a collision would occur, he must skip that plan. If no collision would occur, he may freely choose to either execute or skip the plan.

Find the maximum possible coordinate of Takahashi after all plans have been considered.

Constraints

• 1 \leq N \leq 5 \times 10^4
• 0 \leq M \leq 2 \times 10^5
• -5 \times 10^4 \leq D_i \leq 5 \times 10^4
• D_i \neq 0
• \displaystyle \sum_{i=1}^{N} |D_i| \leq 5 \times 10^4
• -10^9 \leq X_j \leq 10^9
• X_1, X_2, \ldots, X_M are all distinct
• All input values are integers

Sample Input 1

4 2
3 -2 4 -1
2 5

Sample Output 1

0

Sample Input 2

5 0
-3 1 2 -1 4

Sample Output 2

7

Sample Input 3

10 6
2 5 -3 6 -4 7 -8 3 4 -2
-7 8 14 19 -11 25

Sample Output 3

7

Sample Input 4

20 15
5 4 -6 7 -3 8 -10 6 9 -5 4 -7 12 -8 3 11 -9 2 6 -4
-20 -13 -1 10 18 27 35 44 -7 5 14 22 31 40 50

Sample Output 4

4

Sample Input 5

1 1
50000
0

Sample Output 5

0