Problem Statement

In the Kingdom of AtCoder, residents are required to shout their love for takoyaki at A o'clock every day.

Takahashi, who lives in the Kingdom of AtCoder, goes to bed at B o'clock and wakes up at C o'clock every day (in the 24-hour clock). He can shout his love for takoyaki when he is awake, but cannot when he is asleep. Determine whether he can shout his love for takoyaki every day. Here, a day has 24 hours, and his sleeping time is less than 24 hours.

Constraints

• 0\leq A,B,C\lt 24
• A, B, and C are pairwise different.
• All input values are integers.

Sample Input 1

21 8 14

Sample Output 1

Yes

Takahashi goes to bed at 8 o'clock and wakes up at 14 o'clock every day. He is awake at 21 o'clock, so he can shout his love for takoyaki every day. Therefore, print Yes.

Sample Input 2

0 21 7

Sample Output 2

No

Takahashi goes to bed at 21 o'clock and wakes up at 7 o'clock every day. He is not awake at 0 o'clock, so he cannot shout his love for takoyaki every day. Therefore, print No.

Sample Input 3

10 7 17

Sample Output 3

No

Problem Statement

You are given N integers A _ 1,A _ 2,\ldots,A _ N.

If their values are all equal, print Yes; otherwise, print No.

Constraints

• 2\leq N\leq100
• 1\leq A _ i\leq100\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

3
3 2 4

Sample Output 1

No

We have A _ 1\neq A _ 2, so you should print No.

Sample Input 2

4
3 3 3 3

Sample Output 2

Yes

We have A _ 1=A _ 2=A _ 3=A _ 4, so you should print Yes.

Sample Input 3

10
73 8 55 26 97 48 37 47 35 55

Sample Output 3

No

Problem Statement

There are N platforms arranged in a row. The height of the i-th platform from the left is H_i.

Takahashi is initially standing on the leftmost platform.

Since he likes heights, he will repeat the following move as long as possible.

• If the platform he is standing on is not the rightmost one, and the next platform to the right has a height greater than that of the current platform, step onto the next platform.

Find the height of the final platform he will stand on.

Constraints

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

Sample Input 1

5
1 5 10 4 2

Sample Output 1

10

Takahashi is initially standing on the leftmost platform, whose height is 1. The next platform to the right has a height of 5 and is higher than the current platform, so he steps onto it.

He is now standing on the 2-nd platform from the left, whose height is 5. The next platform to the right has a height of 10 and is higher than the current platform, so he steps onto it.

He is now standing on the 3-rd platform from the left, whose height is 10. The next platform to the right has a height of 4 and is lower than the current platform, so he stops moving.

Thus, the height of the final platform Takahashi will stand on is 10.

Sample Input 2

3
100 1000 100000

Sample Output 2

100000

Sample Input 3

4
27 1828 1828 9242

Sample Output 3

1828

Problem Statement

You are given a string S. Find the maximum length of a contiguous substring of S that is a palindrome.
Note that there is always a contiguous substring of S that is a palindrome.

Constraints

• S is a string of length between 2 and 100, inclusive, consisting of uppercase English letters.

Sample Input 1

TOYOTA

Sample Output 1

5

TOYOT, a contiguous substring of TOYOTA, is a palindrome of length 5.
TOYOTA, the only length-6 contiguous substring of TOYOTA, is not a palindrome, so print 5.

Sample Input 2

ABCDEFG

Sample Output 2

1

Every contiguous substring of length 1 is a palindrome.

Sample Input 3

AAAAAAAAAA

Sample Output 3

10

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