Problem Statement

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

Find the number of integers i between 1 and N-2 (inclusive) satisfying A_i < A_{i+1} > A_{i+2}.

Constraints

• 3\le N\le 100
• 1\le A_i\le 100
• All input values are integers.

Sample Input 1

6
3 1 4 1 5 2

Sample Output 1

2

Two values i=2,4 satisfy the condition. Thus, output 2.

Sample Input 2

5
1 1 1 2 1

Sample Output 2

1

Sample Input 3

10
7 3 9 8 10 3 1 5 5 4

Sample Output 3

2

Problem Statement

You are given integers M,D and a string S of length M consisting of G and ..

There are M cells arranged in a row from left to right, numbered 1 through M from the left.

Some of the cells have a guardman standing on them. Specifically, a guardman stands on cell i if S_i= G, and no one stands on cell i if S_i= ..

A cell whose distance from a cell with a guardman is at most D is watched by that guardman. That is, a cell x is watched by a guardman if there exists a cell i such that S_i= G and |x-i|\le D.

Among the M cells, find the number of cells that are not watched.

Constraints

• 0\le D < M \le 100
• D and M are integers.
• S_i is a string of length M consisting of G and ..

Sample Input 1

7 1
.G...GG

Sample Output 1

1

Only cell 4 is not watched.

Sample Input 2

6 5
......

Sample Output 2

6

All cells are not watched.

Sample Input 3

21 2
....G...GG.....G.....

Sample Output 3

6

Problem Statement

You are given an integer N and integer sequences P=(P_1,P_2,\ldots, P_N) and Q=(Q_1,Q_2,\ldots,Q_N), each of which is a permutation of (1,2,\ldots,N).

Find the number of integer sequences that are a permutation of (1,2,\ldots,N) and are lexicographically greater than P and lexicographically less than Q.

Constraints

• 1\le N\le 10
• P and Q are integer sequences that are permutations of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

3
1 3 2
3 1 2

Sample Output 1

2

Two sequences (2,1,3),(2,3,1) satisfy the condition. Thus, output 2.

Sample Input 2

5
5 4 2 1 3
5 1 2 3 4

Sample Output 2

0

There is no permutation of (1,2,3,4,5) satisfying the condition.

Sample Input 3

7
3 6 5 2 7 1 4
4 1 5 7 2 3 6

Sample Output 3

223

Problem Statement

A string consisting of lowercase English letters is called a good string if it satisfies the following condition.

• It can be turned into a palindrome by rewriting at most one character.

For example, a, iwai, and abcdcza are good strings, but abcd and atcoder are not good strings. Note that, in particular, a palindrome is also a good string.

You are given a string S consisting of lowercase English letters.

Find the number of non-empty substrings (contiguous subsequences) of S that are good strings.

Two substrings taken from different positions of S are counted separately even if they are equal as strings.

Constraints

• S is a string of length between 1 and 10^4, inclusive, consisting of lowercase English letters.

Sample Input 1

ababa

Sample Output 1

13

The substring ba from the 2nd through 3rd characters of S and the substring ababa from the 1st through 5th characters are some good strings.

Among the 15 substrings, the good strings are the 13 substrings other than abab from the 1st through 4th characters and baba from the 2nd through 5th characters.

Sample Input 2

atcoder

Sample Output 2

18

Sample Input 3

abccbacbacb

Sample Output 3

40

Problem Statement

You are given a positive integer N and a length-N integer sequence A=(A_1,A_2,\ldots,A_N).

Define f(l,r) as the (arithmetic) mean of A_l,A_{l+1},\ldots,A_r.

Find \displaystyle \sum_{1\le l\le r\le N} f(l,r), modulo 998244353.

Constraints

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

Sample Input 1

2
2 3

Sample Output 1

499122184

We have \displaystyle f(1,1)=2,f(1,2)=\frac{2+3}2=\frac52,f(2,2)=3. Thus, \displaystyle \sum_{1\le l\le r\le N} f(l,r)=2+\frac52+3=\frac{15}2.

\displaystyle \frac{15}2 in modulo-998244353 expression is 499122184, so output 499122184.

Sample Input 2

6
1 2 3 4 5 6

Sample Output 2

499122250

Sample Input 3

9
3 1 4 1 5 9 2 6 5

Sample Output 3

855638200

Problem Statement

You are given a positive integer N and a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

There are variables x,y,c. Initially, x=y=c=0.

For k=1,2,\ldots,N in this order, you perform one of the following operations:

• Operation 1: Increase c by 1 if x < P_k. Then, replace x with \max(x,P_k).
• Operation 2: Increase c by 1 if y < P_k. Then, replace y with \max(y,P_k).

Find the maximum possible final value of c.

Constraints

• 1\le N\le 5\times 10^5
• P is a permutation of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

5
4 3 1 2 5

Sample Output 1

4

By performing the operations as follows, you can achieve c=4:

• For k=1: Perform operation 1. Then, (x,y,c)=(4,0,1).
• For k=2: Perform operation 1. Then, (x,y,c)=(4,0,1).
• For k=3: Perform operation 2. Then, (x,y,c)=(4,1,2).
• For k=4: Perform operation 2. Then, (x,y,c)=(4,2,3).
• For k=5: Perform operation 2. Then, (x,y,c)=(4,5,4).

c cannot be made greater than 4 no matter how you perform the operations, so output 4.

Sample Input 2

6
6 5 4 3 2 1

Sample Output 2

2

Sample Input 3

9
3 6 5 2 7 8 9 1 4

Sample Output 3

7

Problem Statement

You are given an integer N and a string S of length N consisting of o and x.

Find the number, modulo 998244353, of permutations P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) satisfying the following condition.

• For k=1,2,\ldots,N, the following two are equivalent.
  • S_k= o
  • P contains a permutation of (1,2,\ldots,k) as a contiguous subsequence.

Constraints

• 1\le N\le 2000
• S_i is a string of length N consisting of o and x.

Sample Input 1

3
oxo

Sample Output 1

2

P=(1,3,2),(2,3,1) satisfy the condition.

Sample Input 2

7
xxxxxxx

Sample Output 2

0

There is no P satisfying the condition.

Sample Input 3

15
oxxxoxxxxxooxxo

Sample Output 3

1627648