Problem Statement

You are given a sequence of N positive numbers, A = (A_1, A_2, \dots, A_N). Find the sequence B = (B_1, B_2, \dots, B_N) of length N defined as follows.

• For i = 1, 2, \dots, N, define B_i as follows:
  • Let B_i be the most recent position before i where an element equal to A_i appeared. If such a position does not exist, let B_i = -1.
    More precisely, if there exists a positive integer j such that A_i = A_j and j < i, let B_i be the largest such j. If no such j exists, let B_i = -1.

Constraints

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

Sample Input 1

5
1 2 1 1 3

Sample Output 1

-1 -1 1 3 -1

• i = 1: There is no 1 before A_1 = 1, so B_1 = -1.
• i = 2: There is no 2 before A_2 = 2, so B_2 = -1.
• i = 3: The most recent occurrence of 1 before A_3 = 1 is A_1, so B_3 = 1.
• i = 4: The most recent occurrence of 1 before A_4 = 1 is A_3, so B_4 = 3.
• i = 5: There is no 3 before A_5 = 3, so B_5 = -1.

Sample Input 2

4
1 1000000000 1000000000 1

Sample Output 2

-1 -1 2 1

Problem Statement

Person 0, Person 1, \ldots, and Person (N-1) are sitting around a turntable in their counterclockwise order, evenly spaced. Dish p_i is in front of Person i on the table.
You may perform the following operation 0 or more times:

• Rotate the turntable by one N-th of a counterclockwise turn. As a result, the dish that was in front of Person i right before the rotation is now in front of Person (i+1) \bmod N.

When you are finished, Person i is happy if Dish i is in front of Person (i-1) \bmod N, Person i, or Person (i+1) \bmod N.
Find the maximum possible number of happy people.

Constraints

• 3 \leq N \leq 2 \times 10^5
• 0 \leq p_i \leq N-1
• p_i \neq p_j if i \neq j.
• All values in input are integers.

Sample Input 1

4
1 2 0 3

Sample Output 1

4

The figure below shows the table after one operation.

Here, there are four happy people:

• Person 0 is happy because Dish 0 is in front of Person 3\ (=(0-1) \bmod 4);
• Person 1 is happy because Dish 1 is in front of Person 1\ (=1);
• Person 2 is happy because Dish 2 is in front of Person 2\ (=2);
• Person 3 is happy because Dish 3 is in front of Person 0\ (=(3+1) \bmod 4).

There cannot be five or more happy people, so the answer is 4.

Sample Input 2

3
0 1 2

Sample Output 2

3

Sample Input 3

10
3 9 6 1 7 2 8 0 5 4

Sample Output 3

5

Problem Statement

You are given a string S consisting of six types of characters: (, ), [, ], <, >.

A string T is called a colorful bracket sequence if it satisfies the following condition:

It is possible to turn T into an empty string by repeating the following operation any number of times (possibly zero):

• If there exists a contiguous substring of T that is one of (), [], or <>, choose one such substring and delete it.
• If the deleted substring was at the beginning or end of T, the remainder becomes the new T.
• Otherwise, concatenate the part before the deleted substring and the part after the deleted substring, and that becomes the new T.

Determine whether S is a colorful bracket sequence.

Constraints

• S is a string of length between 1 and 2\times 10^5, inclusive.
• S consists of (, ), [, ], <, >.

Sample Input 1

([])<>()

Sample Output 1

Yes

For S=([])<>(), it is possible to turn it into an empty string by repeating the operation as follows:

• Delete the substring [] from the 2nd to the 3rd character in ([])<>(), then concatenate the parts before and after it. The string becomes ()<>().
• Delete the substring () from the 1st to the 2nd character in ()<>(). The string becomes <>().
• Delete the substring <> from the 1st to the 2nd character in <>(). The string becomes ().
• Delete the substring () from the 1st to the 2nd character in (). The string becomes empty.

Thus, S=([])<>() is a colorful bracket sequence, so print Yes.

Sample Input 2

([<)]>

Sample Output 2

No

Since S=([<)]> does not contain (), [], or <> as a contiguous substring, we cannot perform the 1st operation, and in particular S is not a colorful bracket sequence. Therefore, print No.

Sample Input 3

())

Sample Output 3

No

It is impossible to turn S into an empty string by repeating the operations.
Therefore, S is not a colorful bracket sequence, so print No.

Problem Statement

There are infinitely many packs, each containing N cards. In each pack, the i-th card is rare with probability P_i percent. Whether each card is rare is independent of other cards being rare.

You will now open the packs one by one, and obtain all the cards in each opened pack. When you keep opening packs until you have obtained a total of at least X rare cards, find the expected number of packs you will open.

Constraints

• 1 \leq N \leq 5000
• 1 \leq X \leq 5000
• 1 \leq P_i \leq 100
• All input values are integers.

Sample Input 1

2 2
50 100

Sample Output 1

1.5000000000000000

The number of packs opened will be 1 with probability \frac{1}{2}, and 2 with probability \frac{1}{2}.

Sample Input 2

2 3
40 60

Sample Output 2

3.2475579530543811

Sample Input 3

6 3
10 33 33 10 100 10

Sample Output 3

1.8657859189536100

Problem Statement

You are given integers N,A_1,A_2,A_3. Find the number, modulo 998244353, of triples of positive integers (X_1,X_2,X_3) that satisfy all of the following three conditions.

• 1\leq X_i \leq N for every i.
• X_i is a multiple of A_i for every i.
• (X_1 \oplus X_2) \oplus X_3 = 0, where \oplus denotes bitwise xor.

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq A_i \leq 10
• All input values are integers.

Sample Input 1

13 2 3 5

Sample Output 1

4

Four triples (X_1,X_2,X_3) satisfy the conditions: (6,3,5),(6,12,10),(12,6,10),(12,9,5).

Sample Input 2

1000000000000000000 1 1 1

Sample Output 2

426724011

Sample Input 3

31415926535897932 3 8 4

Sample Output 3

759934997