Problem Statement

There is an ultramarathon course totaling 100\;\mathrm{km}. Water stations are set up every 5\;\mathrm{km} along the course, including the start and goal, for a total of 21.

Takahashi is at the N\;\mathrm{km} point of this course. Find the position of the nearest water station to him.

Under the constraints of this problem, it can be proven that the nearest water station is uniquely determined.

Constraints

• 0\leq N\leq100
• N is an integer.

Sample Input 1

53

Sample Output 1

55

Takahashi is at the 53\;\mathrm{km} point of the course. The water station at the 55\;\mathrm{km} point is 2\;\mathrm{km} away, and there is no closer water station. Therefore, you should print 55.

Sample Input 2

21

Sample Output 2

20

Takahashi could also go back the way.

Sample Input 3

100

Sample Output 3

100

There are also water stations at the start and goal. Additionally, Takahashi may already be at a water station.

Problem Statement

You are given a sequence of positive integers of length N: A=(A_1,A_2,\dots,A_N).

Find the sum of the odd-indexed elements of A. That is, find A_1 + A_3 + A_5 + \dots + A_m, where m is the largest odd number not exceeding N.

Constraints

• 1 \le N \le 100
• 1 \le A_i \le 100
• All input values are integers.

Sample Input 1

7
3 1 4 1 5 9 2

Sample Output 1

14

The sum of the odd-indexed elements of A is A_1+A_3+A_5+A_7=3+4+5+2=14.

Sample Input 2

1
100

Sample Output 2

100

Sample Input 3

14
100 10 1 10 100 10 1 10 100 10 1 10 100 10

Sample Output 3

403

Problem Statement

You are given a sequence A=(A_0,A_1,\dots,A_{63}) of length 64 consisting of 0 and 1.

Find A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63}.

Constraints

• A_i is 0 or 1.

Sample Input 1

1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 1

13

A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13.

Sample Input 2

1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0

Sample Output 2

766067858140017173

Problem Statement

We have a sequence of length N consisting of positive integers: A=(A_1,\ldots,A_N). Any two adjacent terms have different values.

Let us insert some numbers into this sequence by the following procedure.

1. If every pair of adjacent terms in A has an absolute difference of 1, terminate the procedure.
2. Let A_i, A_{i+1} be the pair of adjacent terms nearest to the beginning of A whose absolute difference is not 1.
   • If A_i < A_{i+1}, insert A_i+1,A_i+2,\ldots,A_{i+1}-1 between A_i and A_{i+1}.
   • If A_i > A_{i+1}, insert A_i-1,A_i-2,\ldots,A_{i+1}+1 between A_i and A_{i+1}.
3. Return to step 1.

Print the sequence when the procedure ends.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• A_i \neq A_{i+1}
• All values in the input are integers.

Sample Input 1

4
2 5 1 2

Sample Output 1

2 3 4 5 4 3 2 1 2

The initial sequence is (2,5,1,2). The procedure goes as follows.

• Insert 3,4 between the first term 2 and the second term 5, making the sequence (2,3,4,5,1,2).
• Insert 4,3,2 between the fourth term 5 and the fifth term 1, making the sequence (2,3,4,5,4,3,2,1,2).

Sample Input 2

6
3 4 5 6 5 4

Sample Output 2

3 4 5 6 5 4

No insertions may be performed.

Problem Statement

We have a sequence of N numbers: A = (a_1, a_2, \dots, a_N).
Process the Q queries explained below.

• Query i: You are given a pair of integers (x_i, k_i). Let us look at the elements of A one by one from the beginning: a_1, a_2, \dots Which element will be the k_i-th occurrence of the number x_i?
  Print the index of that element, or -1 if there is no such element.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq a_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq x_i \leq 10^9 (1 \leq i \leq Q)
• 1 \leq k_i \leq N (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

6 8
1 1 2 3 1 2
1 1
1 2
1 3
1 4
2 1
2 2
2 3
4 1

Sample Output 1

1
2
5
-1
3
6
-1
-1

1 occurs in A at a_1, a_2, a_5. Thus, the answers to Query 1 through 4 are 1, 2, 5, -1 in this order.

Sample Input 2

3 2
0 1000000000 999999999
1000000000 1
123456789 1

Sample Output 2

2
-1

Problem Statement

There are N giants, named 1 to N. When giant i stands on the ground, their shoulder height is A_i, and their head height is B_i.

You can choose a permutation (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) and stack the N giants according to the following rules:

• First, place giant P_1 on the ground. The giant P_1's shoulder will be at a height of A_{P_1} from the ground, and their head will be at a height of B_{P_1} from the ground.

• For i = 1, 2, \ldots, N - 1 in order, place giant P_{i + 1} on the shoulders of giant P_i. If giant P_i's shoulders are at a height of t from the ground, then giant P_{i + 1}'s shoulders will be at a height of t + A_{P_{i + 1}} from the ground, and their head will be at a height of t + B_{P_{i + 1}} from the ground.

Find the maximum possible height of the head of the topmost giant P_N from the ground.

Constraints

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

Sample Input 1

3
4 10
5 8
2 9

Sample Output 1

18

If (P_1, P_2, P_3) = (2, 1, 3), then measuring from the ground, giant 2 has a shoulder height of 5 and a head height of 8, giant 1 has a shoulder height of 9 and a head height of 15, and giant 3 has a shoulder height of 11 and a head height of 18.

The head height of the topmost giant from the ground cannot be greater than 18, so print 18.

Sample Input 2

5
1 1
1 1
1 1
1 1
1 1

Sample Output 2

5

Sample Input 3

10
690830957 868532399
741145463 930111470
612846445 948344128
540375785 925723427
723092548 925021315
928915367 973970164
563314352 832796216
562681294 868338948
923012648 954764623
691107436 891127278

Sample Output 3

7362669937

Problem Statement

You are given an integer N. Find the number of pairs (i,j) of positive integers at most N that satisfy the following condition:

• i \times j is a square number.

Constraints

• 1 \le N \le 2 \times 10^5
• N is an integer.

Sample Input 1

4

Sample Output 1

6

The six pairs (1,1),(1,4),(2,2),(3,3),(4,1),(4,4) satisfy the condition.

On the other hand, (2,3) does not, since 2 \times 3 =6 is not a square number.

Sample Input 2

254

Sample Output 2

896

Problem Statement

In a coordinate space, we want to place three cubes with a side length of 7 so that the volumes of the regions contained in exactly one, two, three cube(s) are V_1, V_2, V_3, respectively.

For three integers a, b, c, let C(a,b,c) denote the cubic region represented by (a\leq x\leq a+7) \land (b\leq y\leq b+7) \land (c\leq z\leq c+7).

Determine whether there are nine integers a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3 that satisfy all of the following conditions, and find one such tuple if it exists.

• |a_1|, |b_1|, |c_1|, |a_2|, |b_2|, |c_2|, |a_3|, |b_3|, |c_3| \leq 100
• Let C_i = C(a_i, b_i, c_i)\ (i=1,2,3).
  • The volume of the region contained in exactly one of C_1, C_2, C_3 is V_1.
  • The volume of the region contained in exactly two of C_1, C_2, C_3 is V_2.
  • The volume of the region contained in all of C_1, C_2, C_3 is V_3.

Constraints

• 0 \leq V_1, V_2, V_3 \leq 3 \times 7^3
• All input values are integers.

Sample Input 1

840 84 7

Sample Output 1

Yes
0 0 0 0 6 0 6 0 0

Consider the case (a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3) = (0, 0, 0, 0, 6, 0, 6, 0, 0).

The figure represents the positional relationship of C_1, C_2, and C_3, corresponding to the orange, cyan, and green cubes, respectively.

Here,

• All of |a_1|, |b_1|, |c_1|, |a_2|, |b_2|, |c_2|, |a_3|, |b_3|, |c_3| are not greater than 100.
• The region contained in all of C_1, C_2, C_3 is (6\leq x\leq 7)\land (6\leq y\leq 7) \land (0\leq z\leq 7), with a volume of (7-6)\times(7-6)\times(7-0)=7.
• The region contained in exactly two of C_1, C_2, C_3 is ((0\leq x < 6)\land (6\leq y\leq 7) \land (0\leq z\leq 7))\lor((6\leq x\leq 7)\land (0\leq y < 6) \land (0\leq z\leq 7)), with a volume of (6-0)\times(7-6)\times(7-0)\times 2=84.
• The region contained in exactly one of C_1, C_2, C_3 has a volume of 840.

Thus, all conditions are satisfied.

(a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3) = (-10, 0, 0, -10, 0, 6, -10, 6, 1) also satisfies all conditions and would be a valid output.

Sample Input 2

343 34 3

Sample Output 2

No

No nine integers a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3 satisfy all of the conditions.

Problem Statement

There are N buildings numbered 1 to N on a number line.
Building i is at coordinate X_i and has height H_i. The size in directions other than height is negligible.

From a point P with coordinate x and height h, building i is considered visible if there exists a point Q on building i such that the line segment PQ does not intersect with any other building.

Find the maximum height at coordinate 0 from which it is not possible to see all buildings. Height must be non-negative; if it is possible to see all buildings at height 0 at coordinate 0, report -1 instead.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq X_1 < \dots < X_N \leq 10^9
• 1 \leq H_i \leq 10^9
• All input values are integers.

Sample Input 1

3
3 2
5 4
7 5

Sample Output 1

1.500000000000000000

From coordinate 0 and height 1.5, building 3 cannot be seen. If the height is even slightly greater than 1.5, all buildings including building 3 can be seen. Thus, the answer is 1.5.

Sample Input 2

2
1 1
2 100

Sample Output 2

-1

Note that -1.000 or similar outputs would be considered incorrect.

Sample Input 3

3
1 1
2 2
3 3

Sample Output 3

0.000000000000000000

Sample Input 4

4
10 10
17 5
20 100
27 270

Sample Output 4

17.142857142857142350