Problem Statement

Given a length-3 string S consisting of uppercase English letters, print Yes if S equals one of ACE, BDF, CEG, DFA, EGB, FAC, and GBD; print No otherwise.

Constraints

• S is a length-3 string consisting of uppercase English letters.

Sample Input 1

ABC

Sample Output 1

No

When S = ABC, S does not equal any of ACE, BDF, CEG, DFA, EGB, FAC, and GBD, so No should be printed.

Sample Input 2

FAC

Sample Output 2

Yes

Sample Input 3

XYX

Sample Output 3

No

Problem Statement

Takahashi likes full moons.

Let today be day 1. The first day on or after today on which he can see a full moon is day M. After that, he can see a full moon every P days, that is, on day M+P, day M+2P, and so on.

Find the number of days between day 1 and day N, inclusive, on which he can see a full moon.

Constraints

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

Sample Input 1

13 3 5

Sample Output 1

3

He can see a full moon on day 3, 8, 13, 18, and so on.

From day 1 to 13, he can see a full moon on three days: day 3, 8, and 13.

Sample Input 2

5 6 6

Sample Output 2

0

There may be no days he can see a full moon.

Sample Input 3

200000 314 318

Sample Output 3

628

Problem Statement

You are given strings S and T consisting of lowercase English letters. Determine whether T is a (contiguous) substring of S.

A string Y is said to be a (contiguous) substring of X if and only if Y can be obtained by performing the operation below on X zero or more times.

• Do one of the following.
  • Delete the first character in X.
  • Delete the last character in X.

For instance, tag is a (contiguous) substring of voltage, while ace is not a (contiguous) substring of atcoder.

Constraints

• S and T consist of lowercase English letters.
• 1 \le |S|,|T| \le 100 (|X| denotes the length of a string X.)

Sample Input 1

voltage
tag

Sample Output 1

Yes

tag is a (contiguous) substring of voltage.

Sample Input 2

atcoder
ace

Sample Output 2

No

ace is not a (contiguous) substring of atcoder.

Sample Input 3

gorilla
gorillagorillagorilla

Sample Output 3

No

Sample Input 4

toyotasystems
toyotasystems

Sample Output 4

Yes

It is possible that S=T.

Problem Statement

There are 2N people standing in a row, and the person at the i-th position from the left is wearing clothes of color A_i. Here, the clothes have N colors from 1 to N, and exactly two people are wearing clothes of each color.

Find how many of the integers i=1,2,\ldots,N satisfy the following condition:

• There is exactly one person between the two people wearing clothes of color i.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq N
• Each integer from 1 through N appears exactly twice in A.
• All input values are integers.

Sample Input 1

3
1 2 1 3 2 3

Sample Output 1

2

There are two values of i that satisfy the condition: 1 and 3.

In fact, the people wearing clothes of color 1 are at the 1st and 3rd positions from the left, with exactly one person in between.

Sample Input 2

2
1 1 2 2

Sample Output 2

0

There may be no i that satisfies the condition.

Sample Input 3

4
4 3 2 3 2 1 4 1

Sample Output 3

3

Problem Statement

A positive integer not less than 10 whose top digit (the most significant digit) in decimal representation is strictly larger than every other digit in that number is called a Snake number. For example, 31 and 201 are Snake numbers, but 35 and 202 are not.

Find how many Snake numbers exist between L and R, inclusive.

Constraints

• 10 \leq L \leq R \leq 10^{18}
• All input values are integers.

Sample Input 1

97 210

Sample Output 1

6

The Snake numbers between 97 and 210, inclusive, are 97, 98, 100, 200, 201, and 210: there are six.

Sample Input 2

1000 9999

Sample Output 2

2025

Sample Input 3

252509054433933519 760713016476190692

Sample Output 3

221852052834757

Problem Statement

Takahashi has N cards from the card game "AtCoder Magics." The i-th card will be called card i. Each card has two parameters: strength and cost. Card i has a strength of A_i and a cost of C_i.

He does not like weak cards, so he will discard them. Specifically, he will repeat the following operation until it can no longer be performed:

• Choose two cards x and y such that A_x > A_y and C_x < C_y. Discard card y.

It can be proved that the set of remaining cards when the operations can no longer be performed is uniquely determined. Find this set of cards.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i, C_i \leq 10^9
• A_1, A_2, \dots ,A_N are all distinct.
• C_1, C_2, \dots ,C_N are all distinct.
• All input values are integers.

Sample Input 1

3
2 4
1 1
3 2

Sample Output 1

2
2 3

Focusing on cards 1 and 3, we have A_1 < A_3 and C_1 > C_3, so card 1 can be discarded.

No further operations can be performed. At this point, cards 2 and 3 remain, so print them.

Sample Input 2

5
1 1
10 2
100 3
1000 4
10000 5

Sample Output 2

5
1 2 3 4 5

In this case, no cards can be discarded.

Sample Input 3

6
32 101
65 78
2 29
46 55
103 130
52 40

Sample Output 3

4
2 3 5 6

Problem Statement

Takahashi and Aoki are playing a game.

• First, Takahashi chooses an integer between A and B (inclusive) and tells it to Aoki.
• Next, Aoki chooses an integer between C and D (inclusive).
• If the sum of these two integers is a prime, then Aoki wins; otherwise, Takahashi wins.

When the two players play optimally, which player will win?

Constraints

• 1 \leq A \leq B \leq 100
• 1 \leq C \leq D \leq 100
• All values in input are integers.

Sample Input 1

2 3 3 4

Sample Output 1

Aoki

For example, if Takahashi chooses 2, Aoki can choose 3 to make the sum 5, which is a prime.

Sample Input 2

1 100 50 60

Sample Output 2

Takahashi

If they play optimally, Takahashi always wins.

Sample Input 3

3 14 1 5

Sample Output 3

Aoki

Problem Statement

We have an empty sequence A. You will be given Q queries, which should be processed in the order they are given. Each query is of one of the three kinds below:

• 1 x : Append x to the end of A.
• 2 : Print the element at the beginning of A. Then, delete that element. It is guaranteed that A will not empty when this query is given.
• 3 : Sort A in ascending order.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• 0 \leq x \leq 10^9
• A will not be empty when a query 2 is given.
• All values in input are integers.

Sample Input 1

8
1 4
1 3
1 2
1 1
3
2
1 0
2

Sample Output 1

1
2

The i-th line below shows the contents of A after the i-th query is processed in Sample Input 1.

• (4)
• (4, 3)
• (4, 3, 2)
• (4, 3, 2, 1)
• (1, 2, 3, 4)
• (2, 3, 4)
• (2, 3, 4, 0)
• (3, 4, 0)

Sample Input 2

9
1 5
1 5
1 3
2
3
2
1 6
3
2

Sample Output 2

5
3
5

The i-th line below shows the contents of A after the i-th query is processed in Sample Input 2.

• (5)
• (5, 5)
• (5, 5, 3)
• (5, 3)
• (3, 5)
• (5)
• (5, 6)
• (5, 6)
• (6)

Problem Statement

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

For each integer pair (L,R) with 1 \le L \le R \le N, define f(L,R) as follows:

• Start with an empty blackboard. Write the R-L+1 integers A_L, A_{L+1}, \ldots, A_R on the blackboard in order.
• Repeat the following operation until all integers on the blackboard are erased:
  • Choose integers l, r with l \le r such that every integer from l through r appears at least once on the blackboard. Then, erase all integers from l through r that are on the blackboard.
• Let f(L,R) be the minimum number of such operations needed to erase all the integers from the blackboard.

Find \displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R).

Constraints

• 1 \le N \le 3 \times 10^5
• 1 \le A_i \le N
• All input values are integers.

Sample Input 1

4
1 3 1 4

Sample Output 1

16

For example, in the case of (L,R)=(1,4):

• The blackboard has 1,3,1,4.
• Choose (l,r)=(1,1) and erase all occurrences of 1. The blackboard now has 3,4.
• Choose (l,r)=(3,4) and erase all occurrences of 3 and 4. The blackboard becomes empty.
• It cannot be done in fewer than two operations, so f(1,4) = 2.

Similarly, you can find f(2,4)=2, f(1,1)=1, etc.

\displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R) = 16, so print 16.

Sample Input 2

5
3 1 4 2 4

Sample Output 2

23

Sample Input 3

10
5 1 10 9 2 5 6 9 1 6

Sample Output 3

129