Problem Statement

Takahashi is growing a plant. Its height at the time of germination is 0\,\mathrm{cm}. Considering the day of germination as day 0, its height increases by 2^i\,\mathrm{cm} day i's night (0 \le i).

Takahashi's height is H\,\mathrm{cm}.

Every morning, Takahashi measures his height against this plant. Find the first day such that the plant's height is strictly greater than Takahashi's height in the morning.

Constraints

• 1 \leq H \leq 10^{9}
• All input values are integers.

Sample Input 1

54

Sample Output 1

6

The plant's height in the mornings of days 1, 2, 3, 4, 5, 6 will be 1\,\mathrm{cm}, 3\,\mathrm{cm}, 7\,\mathrm{cm}, 15\,\mathrm{cm}, 31\,\mathrm{cm}, 63\,\mathrm{cm}, respectively. The plant becomes taller than Takahashi in the morning day 6, so print 6.

Sample Input 2

7

Sample Output 2

4

The plant's height will be 7\,\mathrm{cm} in the morning of day 3 and 15\,\mathrm{cm} in the morning day 4. The plant becomes taller than Takahashi in the morning of day 4, so print 4. Note that, in the morning of day 3, the plant is as tall as Takahashi, but not taller.

Sample Input 3

262144

Sample Output 3

19

Problem Statement

You are given a positive integer N.

Output N, N-1, \dots, 1 in this order, separated by commas ,.

Constraints

• 1 \leq N \leq 9
• N is an integer.

Sample Input 1

9

Sample Output 1

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

Sample Input 2

5

Sample Output 2

5,4,3,2,1

Sample Input 3

1

Sample Output 3

1

Problem Statement

You are given N sequences A_1, A_2, \ldots, A_N.

The length of sequence A_i is L_i, and A_i = (A_{i,1}, A_{i,2}, \ldots, A_{i,L_i}).

After that, integers X and Y are given. Output the value of A_{X,Y}.

Constraints

• 1 \le N \le 2 \times 10^5
• 1 \le L_i
• The sum of L_i is at most 2 \times 10^5.
• 1 \le A_{i,j} \le 1000
• 1 \le X \le N
• 1 \le Y \le L_X
• All input values are integers.

Sample Input 1

3
3 10 20 30
1 7
4 5 6 7 8
3 4

Sample Output 1

8

We have (A_1, A_2, A_3) = ((10,20,30), (7), (5,6, 7,8)).
Since A_3 = (5, 6, 7, 8) and A_{3,4} = 8, output 8.

Sample Input 2

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

Sample Output 2

2

Since A_2 = (8, 2, 6), we have A_{2,2} = 2.

Sample Input 3

1
5 100 200 300 400 500
1 5

Sample Output 3

500

Problem Statement

There is a linear warehouse, which stores an even number of packages.
The layout of the warehouse is represented by a string S.
The warehouse has |S| sections, numbered 1,2,\dots,|S|, and the string S describes them as follows:

• When the i-th character of S is #, one package is placed in section i.
• When the i-th character of S is ., no package is placed in section i.

The warehouse has a robot, which repeats the following action until there are no more packages in the warehouse:

• Collect two packages from the sections with the smallest section numbers among the sections containing packages. The collected packages are carried out of the warehouse.

For each iteration, determine which sections of the warehouse the two packages that were carried out were originally located.

Constraints

• S is a string consisting of # and . with length between 2 and 1000, inclusive.
• The warehouse stores an even number of packages.
• The warehouse stores at least two packages.

Sample Input 1

.#.##..##.#.###....#

Sample Output 1

2,4
5,8
9,11
13,14
15,20

Packages are stored in sections 2,4,5,8,9,11,13,14,15,20.

• In the 1st iteration, packages from sections 2,4 are carried out.
• In the 2nd iteration, packages from sections 5,8 are carried out.
• In the 3rd iteration, packages from sections 9,11 are carried out.
• In the 4th iteration, packages from sections 13,14 are carried out.
• In the 5th iteration, packages from sections 15,20 are carried out.

Problem Statement

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

Determine whether there exists a non-empty (contiguous) subarray of A that has a repeated value, occurring multiple times in A. If such a subarray exists, find the length of the shortest such subarray.

Constraints

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

Sample Input 1

5
3 9 5 3 1

Sample Output 1

4

(3,9,5,3) and (3,9,5,3,1) satisfy the condition. The shorter one is (3,9,5,3), which has length 4.

Sample Input 2

4
2 5 3 1

Sample Output 2

-1

There is no subarray that satisfies the condition.

Sample Input 3

10
1 1 2 3 5 8 13 21 34 55

Sample Output 3

2

Problem Statement

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

Find the sum of the integers between 1 and K, inclusive, that do not appear in the sequence A.

Constraints

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

Sample Input 1

4 5
1 6 3 1

Sample Output 1

11

Among the integers between 1 and 5, three numbers, 2, 4, and 5, do not appear in A.

Thus, print their sum: 2+4+5=11.

Sample Input 2

1 3
346

Sample Output 2

6

Sample Input 3

10 158260522
877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739

Sample Output 3

12523196466007058

Problem Statement

There are N products labeled 1 to N flowing on a conveyor belt. A Keyence printer is attached to the conveyor belt, and product i enters the range of the printer T_i microseconds from now and leaves it D_i microseconds later.

The Keyence printer can instantly print on one product within the range of the printer (in particular, it is possible to print at the moment the product enters or leaves the range of the printer). However, after printing once, it requires a charge time of 1 microseconds before it can print again. What is the maximum number of products the printer can print on when the product and timing for the printer to print are chosen optimally?

Constraints

• 1\leq N \leq 2\times 10^5
• 1\leq T_i,D_i \leq 10^{18}
• All input values are integers.

Sample Input 1

5
1 1
1 1
2 1
1 2
1 4

Sample Output 1

4

Below, we will simply call the moment t microseconds from now time t.

For example, you can print on four products as follows:

• Time 1 : Products 1,2,4,5 enter the range of the printer. Print on product 4.
• Time 2 : Product 3 enters the range of the printer, and products 1,2 leave the range of the printer. Print on product 1.
• Time 3 : Products 3,4 leave the range of the printer. Print on product 3.
• Time 4.5 : Print on product 5.
• Time 5 : Product 5 leaves the range of the printer.

It is impossible to print on all five products, so the answer is 4.

Sample Input 2

2
1 1
1000000000000000000 1000000000000000000

Sample Output 2

2

Sample Input 3

10
4 1
1 2
1 4
3 2
5 1
5 1
4 1
2 1
4 1
2 4

Sample Output 3

6

Problem Statement

You are given a simple connected undirected graph G with N vertices and M edges.
The vertices and edges of G are numbered as vertices 1,2,\ldots,N and edges 1,2,\ldots,M, respectively, and edge i connects vertices U_i and V_i.
You can move bidirectionally between vertices connected by an edge in time 1.

Additionally, each vertex is either safe or dangerous, and this state is given by a string S of length N consisting of S and D.
Specifically, vertex i is safe when the i-th character (1\leq i\leq N) of S is S, and vertex i is dangerous when it is D.
It is guaranteed that there are at least two safe vertices and at least one dangerous vertex.

For each dangerous vertex v, find the following value:

The minimum possible time to start from some safe vertex, pass through v, and move to a safe vertex different from the starting vertex.

Constraints

• 3\leq N\leq 2\times 10^5
• N-1\leq M\leq 2\times 10^5
• 1\leq U_i,V_i\leq N
• U_i\neq V_i
• If i\neq j, then \{ U_i,V_i \}\neq \{ U_j,V_j \}.
• S is a string of length N consisting of S and D.
• N,M,U_i,V_i are all integers.
• G is connected.
• There are at least two safe vertices.
• There is at least one dangerous vertex.

Sample Input 1

5 5
1 2
1 3
2 3
3 4
4 5
SSDDS

Sample Output 1

2
3

The dangerous vertices are (in ascending order of vertex number) vertices 3 and 4.

For vertex 3, moving from vertex 1 \to vertex 3 \to vertex 2 (for example) satisfies the condition.
The time required for this movement is 2, and this is the minimum.
Therefore, print 2 on the 1st line.

For vertex 4, moving from vertex 1 \to vertex 3 \to vertex 4 \to vertex 5 (for example) satisfies the condition.
The time required for this movement is 3, and there is no way to move that satisfies the condition with time 2 or less, so this is the minimum.
Therefore, print 3 on the 2nd line.

Sample Input 2

3 2
1 2
2 3
SSD

Sample Output 2

3

The dangerous vertex is vertex 3.

Moving from vertex 1 \to vertex 2 \to vertex 3 \to vertex 2 (for example) satisfies the condition.
The time required for this movement is 3, and this is the minimum.
Note that movements such as vertex 2 \to vertex 3 \to vertex 2 do not satisfy the condition that the destination is "different from the starting vertex".

Problem Statement

A monster with health H has appeared in front of you, and a turn-based battle has started.

In each turn 1,2,…, you cast one of N spells, spells 1,…,N.

If you cast spell i in turn j, the monster's health reduces by d_i in each turn j,j+1,…,j+t_i －1.

Find the earliest turn that you can make the monster's health 0 or less.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq H \leq 10^{18}
• 1 \leq t_i,d_i \leq 10^9
• All values in the input are integers.

Sample Input 1

2 20
2 2
5 1

Sample Output 1

6

The following procedure makes the monster's health 0 or less in turn 6, which is the earliest.

• Cast spell 1 in turn 1. Due to the spell cast in turn 1, the monster's health reduces by 2 and becomes 18.
• Cast spell 2 in turn 2. Due to the spells cast in turns 1 and 2, the monster's health reduces by 2+1=3 and becomes 15.
• Cast spell 1 in turn 3. Due to the spells cast in turns 2 and 3, the monster's health reduces by 1+2=3 and becomes 12.
• Cast spell 2 in turn 4. Due to the spells cast in turns 2,3 and 4, the monster's health reduces by 1+2+1=4 and becomes 8.
• Cast spell 1 in turn 5. Due to the spells cast in turns 2,4 and 5, the monster's health reduces by 1+1+2=4 and becomes 4.
• Cast spell 2 in turn 6. Due to the spells cast in turns 2,4,5 and 6, the monster's health reduces by 1+1+2+1=5 and becomes -1.

Sample Input 2

10 200
1 21
1 1
1 1
8 4
30 1
3 1
10 2
8 1
9 1
4 4

Sample Output 2

9