Problem Statement

In the Kingdom of AtCoder, there is a standardized test of competitive programming proficiency.

An examinee will get a score out of 100 and obtain a rank according to the score, as follows:

• Novice, for a score not less than 0 but less than 40;
• Intermediate, for a score not less than 40 but less than 70;
• Advanced, for a score not less than 70 but less than 90;
• Expert, for a score not less than 90.

Takahashi took this test and got X points.

Find the minimum number of extra points needed to go up one rank higher. If, however, his rank was Expert, print expert, as there is no higher rank than that.

Constraints

• 0 \leq X \leq 100
• X is an integer.

Sample Input 1

56

Sample Output 1

14

He got 56 points and was certified as Intermediate. In order to reach the next rank of Advanced, he needs at least 14 more points.

Sample Input 2

32

Sample Output 2

8

Sample Input 3

0

Sample Output 3

40

Sample Input 4

100

Sample Output 4

expert

He got full points and was certified as Expert. There is no rank higher than that, so print expert.

Problem Statement

You are given a string S consisting of lowercase English letters. The length of S is between 3 and 100, inclusive.

All characters but one of S are the same.

Find x such that the x-th character of S differs from all other characters.

Constraints

• S is a string of length between 3 and 100, inclusive, consisting of two different lowercase English letters.
• All characters but one of S are the same.

Sample Input 1

yay

Sample Output 1

2

The second character of yay differs from the first and third characters.

Sample Input 2

egg

Sample Output 2

1

Sample Input 3

zzzzzwz

Sample Output 3

6

Problem Statement

Takahashi is playing a game called Chess960. He has decided to write a code that determines if a random initial state satisfies the conditions of Chess960.

You are given a string S of length eight. S has exactly one K and Q, and exactly two R's, B's , and N's. Determine if S satisfies all of the following conditions.

• Suppose that the x-th and y-th (x < y) characters from the left of S are B; then, x and y have different parities.

• K is between two R's. More formally, suppose that the x-th and y-th (x < y) characters from the left of S are R and the z-th is K; then x< z < y.

Constraints

• S is a string of length 8 that contains exactly one K and Q, and exactly two R's, B's , and N's.

Sample Input 1

RNBQKBNR

Sample Output 1

Yes

The 3-rd and 6-th characters are B, and 3 and 6 have different parities. Also, K is between the two R's. Thus, the conditions are fulfilled.

Sample Input 2

KRRBBNNQ

Sample Output 2

No

K is not between the two R's.

Sample Input 3

BRKRBQNN

Sample Output 3

No

Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

• N is an integer between 1 and 1000, inclusive.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.

Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.

Sample Input 3

8
national

Sample Output 3

nyationyal

Problem Statement

You have an empty sequence and N balls. The size of the i-th ball (1 \leq i \leq N) is 2^{A_i}.

You will perform N operations.
In the i-th operation, you add the i-th ball to the right end of the sequence, and repeat the following steps:

1. If the sequence has one or fewer balls, end the operation.
2. If the rightmost ball and the second rightmost ball in the sequence have different sizes, end the operation.
3. If the rightmost ball and the second rightmost ball in the sequence have the same size, remove these two balls and add a new ball to the right end of the sequence with a size equal to the sum of the sizes of the two removed balls. Then, go back to step 1 and repeat the process.

Determine the number of balls remaining in the sequence after the N operations.

Constraints

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

Sample Input 1

7
2 1 1 3 5 3 3

Sample Output 1

3

The operations proceed as follows:

• After the first operation, the sequence has one ball, of size 2^2.
• After the second operation, the sequence has two balls, of sizes 2^2 and 2^1 in order.
• After the third operation, the sequence has one ball, of size 2^3. This is obtained as follows:
  • When the third ball is added during the third operation, the sequence has balls of sizes 2^2, 2^1, 2^1 in order.
  • The first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^1 + 2^1 = 2^2 is added. Now, the sequence has balls of sizes 2^2, 2^2.
  • Again, the first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^2 + 2^2 = 2^3 is added, leaving the sequence with a ball of size 2^3.
• After the fourth operation, the sequence has one ball, of size 2^4.
• After the fifth operation, the sequence has two balls, of sizes 2^4 and 2^5 in order.
• After the sixth operation, the sequence has three balls, of sizes 2^4, 2^5, 2^3 in order.
• After the seventh operation, the sequence has three balls, of sizes 2^4, 2^5, 2^4 in order.

Therefore, you should print 3, the final number of balls in the sequence.

Sample Input 2

5
0 0 0 1 2

Sample Output 2

4

The operations proceed as follows:

• After the first operation, the sequence has one ball, of size 2^0.
• After the second operation, the sequence has one ball, of size 2^1.
• After the third operation, the sequence has two balls, of sizes 2^1 and 2^0 in order.
• After the fourth operation, the sequence has three balls, of sizes 2^1, 2^0, 2^1 in order.
• After the fifth operation, the sequence has four balls, of sizes 2^1, 2^0, 2^1, 2^2 in order.

Therefore, you should print 4, the final number of balls in the sequence.