Problem Statement

You are given N integers A_1, A_2, \ldots, A_N. Find the largest among those integers that are not the largest.

The constraints of this problem guarantee that the answer exists.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• It is not the case that all A_1, A_2, \ldots, A_N are equal.
• All input values are integers.

Sample Input 1

5
2 1 3 3 2

Sample Output 1

2

The largest integer among 2,1,3,3,2 is 3.

The integers that are not 3 among 2,1,3,3,2 are 2,1,2, among which the largest is 2.

Sample Input 2

4
4 3 2 1

Sample Output 2

3

Sample Input 3

8
22 22 18 16 22 18 18 22

Sample Output 3

18

Problem Statement

You are given N types of strings S_1,S_2,\ldots,S_N.

You perform the following operation once:

• Choose distinct integers i and j\ (1\le i\le N,1\le j\le N) and concatenate S_i and S_j in this order.

How many different strings can be obtained as a result of this operation?

If different choices of (i,j) result in the same concatenated string, it is counted as one string.

Constraints

• 2\le N\le100
• N is an integer.
• S_i is a string of length between 1 and 10, inclusive, consisting of lowercase English letters.
• S_i\ne S_j\ (1\le i\lt j\le N)

Sample Input 1

4
at
atco
coder
der

Sample Output 1

11

The possible strings are atatco, atcoat, atcoder, atcocoder, atder, coderat, coderatco, coderder, derat, deratco, dercoder, which are 11 strings.

Thus, print 11.

Sample Input 2

5
a
aa
aaa
aaaa
aaaaa

Sample Output 2

7

The possible strings are aaa, aaaa, aaaaa, aaaaaa, aaaaaaa, aaaaaaaa, aaaaaaaaa, which are 7 strings.

Thus, print 7.

Sample Input 3

10
armiearggc
ukupaunpiy
cogzmjmiob
rtwbvmtruq
qapfzsitbl
vhkihnipny
ybonzypnsn
esxvgoudra
usngxmaqpt
yfseonwhgp

Sample Output 3

90

Problem Statement

There are N mochi (rice cakes) arranged in ascending order of size. The size of the i-th mochi (1 \leq i \leq N) is A_i.

Given two mochi A and B, with sizes a and b respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi A on top of mochi B if and only if a is at most half of b.

You choose two mochi out of the N mochi, and place one on top of the other to form one kagamimochi.

Find how many different kinds of kagamimochi can be made.

Two kagamimochi are distinguished if at least one of the mochi is different, even if the sizes of the mochi are the same.

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
• A_i \leq A_{i+1} \ (1 \leq i < N)
• All input values are integers.

Sample Input 1

6
2 3 4 4 7 10

Sample Output 1

8

The sizes of the given mochi are as follows:

In this case, you can make the following eight kinds of kagamimochi:

Note that there are two kinds of kagamimochi where a mochi of size 4 is topped by a mochi of size 2, and two kinds where a mochi of size 10 is topped by a mochi of size 4.

Sample Input 2

3
387 388 389

Sample Output 2

0

It is possible that you cannot make any kagamimochi.

Sample Input 3

32
1 2 4 5 8 10 12 16 19 25 33 40 50 64 87 101 149 175 202 211 278 314 355 405 412 420 442 481 512 582 600 641

Sample Output 3

388

Problem Statement

Takahashi is on a two-dimensional plane. Starting from the origin, he made N moves.

The N moves are represented by a string of length N as described below:

• Takahashi's coordinates after the i-th move are:

  • (x+1,y) if the i-th character of S is R;
  • (x-1,y) if the i-th character of S is L;
  • (x,y+1) if the i-th character of S is U; and
  • (x,y-1) if the i-th character of S is D,

  where (x,y) is his coordinates before the move.

Determine if Takahashi visited the same coordinates multiple times in the course of the N moves (including the starting and ending points).

Constraints

• 1 \leq N \leq 2\times 10^5
• N is an integer.
• S is a string of length N consisting of R, L, U, and D.

Sample Input 1

5
RLURU

Sample Output 1

Yes

Takahashi's coordinates change as follows: (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2).

Sample Input 2

20
URDDLLUUURRRDDDDLLLL

Sample Output 2

No

Problem Statement

There is a grid with 10^9 by 10^9 squares. Let (i, j) denote the square at the (i + 1)-th row from the top and the (j + 1)-th column from the left (0 \leq i, j \lt 10^9). (Note the unusual index assignment.)
Each square is black or white. The color of the square (i, j) is represented by a character P[i \bmod N][j \bmod N], where B means black, and W means white. Here, a \bmod b denotes the remainder when a is divided by b.

Answer Q queries.
Each query gives you four integers A, B, C, D and asks you to find the number of black squares contained in the rectangular area with (A, B) as the top-left corner and (C, D) as the bottom-right corner.

Constraints

• 1 \leq N \leq 1000
• P[i][j] is W or B.
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq A \leq C \lt 10^9
• 0 \leq B \leq D \lt 10^9
• N, Q, A, B, C, D are all integers.

Sample Input 1

3 2
WWB
BBW
WBW
1 2 3 4
0 3 4 5

Sample Output 1

4
7

The figure below illustrates the upper left part of the grid.

For the first query, the rectangular area with (1, 2) as the top-left corner and (3, 4) as the bottom-right corner, surrounded by the red frame in the figure, contains four black squares.
For the second query, the rectangular area with (0, 3) as the top-left corner and (4, 5) as the bottom-right corner, surrounded by the blue frame in the figure, contains seven black squares.

Sample Input 2

10 5
BBBWWWBBBW
WWWWWBBBWB
BBBWBBWBBB
BBBWWBWWWW
WWWWBWBWBW
WBBWBWBBBB
WWBBBWWBWB
WBWBWWBBBB
WBWBWBBWWW
WWWBWWBWWB
5 21 21 93
35 35 70 43
55 72 61 84
36 33 46 95
0 0 999999999 999999999

Sample Output 2

621
167
44
344
500000000000000000