Problem Statement

You are given N integers A_1, A_2, \dots, A_N. Also, define B_i = A_i \times A_{i+1}\ (1 \leq i \leq N-1).

Print B_1, B_2, \dots, B_{N-1} in this order, separated by spaces.

Constraints

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

Sample Input 1

3
3 4 6

Sample Output 1

12 24

We have B_1 = A_1 \times A_2 = 12, B_2 = A_2 \times A_3 = 24.

Sample Input 2

5
22 75 26 45 72

Sample Output 2

1650 1950 1170 3240

Problem Statement

There is an infinitely long piano keyboard. Is there a continuous segment within this keyboard that consists of W white keys and B black keys?

Let S be the string formed by infinitely repeating the string wbwbwwbwbwbw.

Is there a substring of S that consists of W occurrences of w and B occurrences of b?

Constraints

• W and B are integers.
• 0\leq W,B \leq 100
• W+B \geq 1

Sample Input 1

3 2

Sample Output 1

Yes

The first 15 characters of S are wbwbwwbwbwbwwbw. You can take the 11-th through 15-th characters to form the string bwwbw, which is a substring consisting of three occurrences of w and two occurrences of b.

Sample Input 2

3 0

Sample Output 2

No

The only string consisting of three occurrences of w and zero occurrences of b is www, which is not a substring of S.

Sample Input 3

92 66

Sample Output 3

Yes

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

You are given a string S of length N consisting of 0 and 1.

A string T of length N consisting of 0 and 1 is a good string if and only if it satisfies the following condition:

• There is exactly one integer i such that 1 \leq i \leq N - 1 and the i-th and (i + 1)-th characters of T are the same.

For each i = 1,2,\ldots, N, you can choose whether or not to perform the following operation once:

• If the i-th character of S is 0, replace it with 1, and vice versa. The cost of this operation, if performed, is C_i.

Find the minimum total cost required to make S a good string.

Constraints

• 2 \leq N \leq 2 \times 10^5
• S is a string of length N consisting of 0 and 1.
• 1 \leq C_i \leq 10^9
• N and C_i are integers.

Sample Input 1

5
00011
3 9 2 6 4

Sample Output 1

7

Performing the operation for i = 1, 5 and not performing it for i = 2, 3, 4 makes S = 10010, which is a good string. The cost incurred in this case is 7, and it is impossible to make S a good string for less than 7, so print 7.

Sample Input 2

4
1001
1 2 3 4

Sample Output 2

0

Sample Input 3

11
11111100111
512298012 821282085 543342199 868532399 690830957 973970164 928915367 954764623 923012648 540375785 925723427

Sample Output 3

2286846953

Problem Statement

There is a grid with H rows and W columns. Initially, all cells are painted with color 0.

You will perform the following operations in the order i = 1, 2, \ldots, M.

• If T_i = 1, repaint all cells in the A_i-th row with color X_i.

• If T_i = 2, repaint all cells in the A_i-th column with color X_i.

After all operations are completed, for each color i that exists on the grid, find the number of cells that are painted with color i.

Constraints

• 1 \leq H, W, M \leq 2 \times 10^5
• T_i \in \lbrace 1, 2 \rbrace
• 1 \leq A_i \leq H for each i such that T_i = 1,
• 1 \leq A_i \leq W for each i such that T_i = 2.
• 0 \leq X_i \leq 2 \times 10^5
• All input values are integers.

Sample Input 1

3 4 4
1 2 5
2 4 0
1 3 3
1 3 2

Sample Output 1

3
0 5
2 4
5 3

The operations will change the colors of the cells in the grid as follows:

0000   0000   0000   0000   0000
0000 → 5555 → 5550 → 5550 → 5550 
0000   0000   0000   3333   2222

Eventually, there are five cells painted with color 0, four with color 2, and three with color 5.

Sample Input 2

1 1 5
1 1 1
1 1 10
2 1 100
1 1 1000
2 1 10000

Sample Output 2

1
10000 1

Sample Input 3

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

Sample Output 3

5
6 5
7 5
8 5
9 5
10 5

Problem Statement

For a string X of length n, let f(X,k) denote the string obtained by repeating k times the string X, and g(X,k) denote the string obtained by repeating k times the first character, the second character, \dots, the n-th character of X, in this order. For example, if X= abc, then f(X,2)= abcabc, and g(X,3)= aaabbbccc. Also, for any string X, both f(X,0) and g(X,0) are empty strings.

You are given a positive integer N and strings S and T. Find the largest non-negative integer k such that g(T,k) is a (not necessarily contiguous) subsequence of f(S,N). Note that g(T,0) is always a subsequence of f(S,N) by definition.

Constraints

• N is an integer.
• 1\leq N\leq 10^{12}
• S and T are strings consisting of lowercase English letters with lengths between 1 and 10^5, inclusive.

Sample Input 1

3
abc
ab

Sample Output 1

2

We have f(S,3)= abcabcabc. g(T,2)= aabb is a subsequence of f(S,3), but g(T,3)= aaabbb is not, so print 2.

Sample Input 2

3
abc
arc

Sample Output 2

0

Sample Input 3

1000000000000
kzazkakxkk
azakxk

Sample Output 3

344827586207

Problem Statement

You are given an integer sequence A = (A_1, A_2, \ldots, A_N).

Find the number of pairs of integers (L, R) that satisfy the following conditions:

• 1 \leq L \leq R \leq N
• There is a number that appears exactly once among A_L, A_{L + 1}, \ldots, A_R. More precisely, there is an integer x such that exactly one integer i satisfies A_i = x and L \leq i \leq R.

Constraints

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

Sample Input 1

5
2 2 1 2 1

Sample Output 1

12

12 pairs of integers satisfy the conditions: (L, R) = (1, 1), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5), (5, 5).

Sample Input 2

4
4 4 4 4

Sample Output 2

4

Sample Input 3

10
1 2 1 4 3 3 3 2 2 4

Sample Output 3

47