CodeEff/ECCO huggingface dataset:
Problem Description: Score : 600 points
Problem Statement
Takahashi has
N
cards. The
i
-th of these cards has an integer
A_i
written on it.
Takahashi will choose an integer
K
, and then repeat the following operation some number of times:
Choose exactly
K
cards such that the integers written on them are all different, and eat those cards. (The eaten cards disappear.)
For each
K = 1,2, \ldots, N
, find the maximum number of times Takahashi can do the operation.
Constraints
1 \le N \le 3 \times 10^5
1 \le A_i \le N
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1
A_2
\ldots
A_N
Output
Print
N
integers.
The
t
-th
(1 \le t \le N)
of them should be the answer for the case
K=t
.
Sample Input 1
3
2 1 2
Sample Output 1
3
1
0
For
K = 1
, we can do the operation as follows:
Choose the first card to eat.
Choose the second card to eat.
Choose the third card to eat.
For
K = 2
, we can do the operation as follows:
Choose the first and second cards to eat.
For
K = 3
, we cannot do the operation at all. Note that we cannot choose the first and third cards at the same time.
Sample Input 2
5
1 2 3 4 5
Sample Output 2
5
2
1
1
1
Sample Input 3
4
1 3 3 3
Sample Output 3
4
1
0
0
Problem Description: Score : 300 points
Problem Statement
Given is a string
S
. Let
T
be the concatenation of
K
copies of
S
.
We can repeatedly perform the following operation: choose a character in
T
and replace it with a different character.
Find the minimum number of operations required to satisfy the following condition: any two adjacent characters in
T
are different.
Constraints
1 \leq |S| \leq 100
S
consists of lowercase English letters.
1 \leq K \leq 10^9
K
is an integer.
Input
Input is given from Standard Input in the following format:
S
K
Output
Print the minimum number of operations required.
Sample Input 1
issii
2
Sample Output 1
4
T
is
issiiissii
.  For example, we can rewrite it into
ispiqisyhi
, and now any two adjacent characters are different.
Sample Input 2
qq
81
Sample Output 2
81
Sample Input 3
cooooooooonteeeeeeeeeest
999993333
Sample Output 3
8999939997
Problem Description: Score : 500 points
Problem Statement
Given is a connected undirected graph with
N
vertices and
M
edges. The vertices are numbered
1
to
N
, and the edges are described by a grid of characters
S
.
If
S_{i,j}
is
1
, there is an edge connecting Vertex
i
and
j
; otherwise, there is no such edge.
Determine whether it is possible to divide the vertices into non-empty sets
V_1, \dots, V_k
such that the following condition is satisfied. If the answer is yes, find the maximum possible number of sets,
k
, in such a division.
Every edge connects two vertices belonging to two "adjacent" sets. More formally, for every edge
(i,j)
, there exists
1\leq t\leq k-1
such that
i\in V_t,j\in V_{t+1}
or
i\in V_{t+1},j\in V_t
holds.
Constraints
2 \leq N \leq 200
S_{i,j}
is
0
or
1
.
S_{i,i}
is
0
.
S_{i,j}=S_{j,i}
The given graph is connected.
N
is an integer.
Input
Input is given from Standard Input in the following format:
N
S_{1,1}...S_{1,N}
:
S_{N,1}...S_{N,N}
Output
If it is impossible to divide the vertices into sets so that the condition is satisfied, print
-1
.
Otherwise, print the maximum possible number of sets,
k
, in a division that satisfies the condition.
Sample Input 1
2
01
10
Sample Output 1
2
We can put Vertex
1
in
V_1
and Vertex
2
in
V_2
.
Sample Input 2
3
011
101
110
Sample Output 2
-1
Sample Input 3
6
010110
101001
010100
101000
100000
010000
Sample Output 3
4
Problem Description: Score : 800 points
Problem Statement
Given are integers
N
and
X
. For each integer
k
between
0
and
X
(inclusive), find the answer to the following question, then compute the sum of all those answers, modulo
998244353
.
Let us repeat the following operation on the integer
k
. Operation: if the integer is currently odd, subtract
1
from it and divide it by
2
; otherwise, divide it by
2
and add
2^{N-1}
to it. How many operations need to be performed until
k
returns to its original value? (The answer is considered to be
0
if
k
never returns to its original value.)
Constraints
1 \leq N \leq 2\times 10^5
0 \leq X < 2^N
X
is given in binary and has exactly
N
digits. (In case
X
has less than
N
digits, it is given with leading zeroes.)
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
X
Output
Print the sum of the answers to the questions for the integers between
0
and
X
(inclusive), modulo
998244353
.
Sample Input 1
3
111
Sample Output 1
40
For example, for
k=3
, the operation changes
k
as follows:
1,0,4,6,7,3
. Therefore the answer for
k=3
is
6
.
Sample Input 2
6
110101
Sample Output 2
616
Sample Input 3
30
001110011011011101010111011100
Sample Output 3
549320998
Problem Description: Score : 200 points
Problem Statement
N
friends of Takahashi has come to a theme park.
To ride the most popular roller coaster in the park, you must be at least
K
centimeters tall.
The
i
-th friend is
h_i
centimeters tall.
How many of the Takahashi's friends can ride the roller coaster?
Constraints
1 \le N \le 10^5
1 \le K \le 500
1 \le h_i \le 500
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
K
h_1
h_2
\ldots
h_N
Output
Print the number of people among the Takahashi's friends who can ride the roller coaster.
Sample Input 1
4 150
150 140 100 200
Sample Output 1
2
Two of them can ride the roller coaster: the first and fourth friends.
Sample Input 2
1 500
499
Sample Output 2
0
Sample Input 3
5 1
100 200 300 400 500
Sample Output 3
5
Problem Description: Score : 300 points
Problem Statement
Takahashi is a teacher responsible for a class of
N
students.
The students are given distinct student numbers from
1
to
N
.
Today, all the students entered the classroom at different times.
According to Takahashi's record, there were
A_i
students in the classroom when student number
i
entered the classroom (including student number
i
).
From these records, reconstruct the order in which the students entered the classroom.
Constraints
1 \le N \le 10^5
1 \le A_i \le N
A_i \neq A_j
(i \neq j)
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1
A_2
\ldots
A_N
Output
Print the student numbers of the students in the order the students entered the classroom.
Sample Input 1
3
2 3 1
Sample Output 1
3 1 2
First, student number
3
entered the classroom.
Then, student number
1
entered the classroom.
Finally, student number
2
entered the classroom.
Sample Input 2
5
1 2 3 4 5
Sample Output 2
1 2 3 4 5
Sample Input 3
8
8 2 7 3 4 5 6 1
Sample Output 3
8 2 4 5 6 7 3 1
Problem Description: Score : 600 points
Problem Statement
Given is a directed graph
G
with
N
vertices and
M
edges.
The vertices are numbered
1
to
N
, and the
i
-th edge is directed from Vertex
A_i
to Vertex
B_i
.
It is guaranteed that the graph contains no self-loops or multiple edges.
Determine whether there exists an induced subgraph (see Notes) of
G
such that the in-degree and out-degree of every vertex are both
1
. If the answer is yes, show one such subgraph.
Here the null graph is not considered as a subgraph.
Notes
For a directed graph
G = (V, E)
, we call a directed graph
G' = (V', E')
satisfying the following conditions an induced subgraph of
G
:
V'
is a (non-empty) subset of
V
.
E'
is the set of all the edges in
E
that have both endpoints in
V'
.
Constraints
1 \leq N \leq 1000
0 \leq M \leq 2000
1 \leq A_i,B_i \leq N
A_i \neq B_i
All pairs
(A_i, B_i)
are distinct.
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
M
A_1
B_1
A_2
B_2
:
A_M
B_M
Output
If there is no induced subgraph of
G
that satisfies the condition, print
-1
.
Otherwise, print an induced subgraph of
G
that satisfies the condition, in the following format:
K
v_1
v_2
:
v_K
This represents the induced subgraph of
G
with
K
vertices whose vertex set is
\{v_1, v_2, \ldots, v_K\}
. (The order of
v_1, v_2, \ldots, v_K
does not matter.)
If there are multiple subgraphs of
G
that satisfy the condition, printing any of them is accepted.
Sample Input 1
4 5
1 2
2 3
2 4
4 1
4 3
Sample Output 1
3
1
2
4
The induced subgraph of
G
whose vertex set is
\{1, 2, 4\}
has the edge set
\{(1, 2), (2, 4), (4, 1)\}
. The in-degree and out-degree of every vertex in this graph are both
1
.
Sample Input 2
4 5
1 2
2 3
2 4
1 4
4 3
Sample Output 2
-1
There is no induced subgraph of
G
that satisfies the condition.
Sample Input 3
6 9
1 2
2 3
3 4
4 5
5 6
5 1
5 2
6 1
6 2
Sample Output 3
4
2
3
4
5
Problem Description: Score : 700 points
Problem Statement
Snuke has a permutation
(P_0,P_1,\cdots,P_{N-1})
of
(0,1,\cdots,N-1)
.
Now, he will perform the following operation
exactly once
:
Choose
K
consecutive elements in
P
and sort them in ascending order.
Find the number of permutations that can be produced as
P
after the operation.
Constraints
2 \leq N \leq 200000
2 \leq K \leq N
0 \leq P_i \leq N-1
P_0,P_1,\cdots,P_{N-1}
are all different.
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
K
P_0
P_1
\cdots
P_{N-1}
Output
Print the number of permutations that can be produced as
P
after the operation.
Sample Input 1
5 3
0 2 1 4 3
Sample Output 1
2
Two permutations can be produced as
P
after the operation:
(0,1,2,4,3)
and
(0,2,1,3,4)
.
Sample Input 2
4 4
0 1 2 3
Sample Output 2
1
Sample Input 3
10 4
2 0 1 3 7 5 4 6 8 9
Sample Output 3
6
Problem Description: Score : 700 points
Problem Statement
We have an integer sequence of length
N
:
A_0,A_1,\cdots,A_{N-1}
.
Find the following sum (
\mathrm{lcm}(a, b)
denotes the least common multiple of
a
and
b
):
\sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} \mathrm{lcm}(A_i,A_j)
Since the answer may be enormous, compute it modulo
998244353
.
Constraints
1 \leq N \leq 200000
1 \leq A_i \leq 1000000
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_0\ A_1\ \cdots\ A_{N-1}
Output
Print the sum modulo
998244353
.
Sample Input 1
3
2 4 6
Sample Output 1
22
\mathrm{lcm}(2,4)+\mathrm{lcm}(2,6)+\mathrm{lcm}(4,6)=4+6+12=22
.
Sample Input 2
8
1 2 3 4 6 8 12 12
Sample Output 2
313
Sample Input 3
10
356822 296174 484500 710640 518322 888250 259161 609120 592348 713644
Sample Output 3
353891724
Problem Description: Score: 100 points
Problem Statement
The weather in Takahashi's town changes day by day, in the following cycle: Sunny, Cloudy, Rainy, Sunny, Cloudy, Rainy, ...
Given is a string
S
representing the weather in the town today. Predict the weather tomorrow.
Constraints
S
is
Sunny
,
Cloudy
, or
Rainy
.
Input
Input is given from Standard Input in the following format:
S
Output
Print a string representing the expected weather tomorrow, in the same format in which input is given.
Sample Input 1
Sunny
Sample Output 1
Cloudy
In Takahashi's town, a sunny day is followed by a cloudy day.
Sample Input 2
Rainy
Sample Output 2
Sunny
Problem Description: Score: 200 points
Problem Statement
Takahashi will do a tap dance. The dance is described by a string
S
where each character is
L
,
R
,
U
, or
D
. These characters indicate the positions on which Takahashi should step. He will follow these instructions one by one in order, starting with the first character.
S
is said to be
easily playable
if and only if it satisfies both of the following conditions:
Every character in an odd position (
1
-st,
3
-rd,
5
-th,
\ldots
) is
R
,
U
, or
D
.
Every character in an even position (
2
-nd,
4
-th,
6
-th,
\ldots
) is
L
,
U
, or
D
.
Your task is to print
Yes
if
S
is easily playable, and
No
otherwise.
Constraints
S
is a string of length between
1
and
100
(inclusive).
Each character of
S
is
L
,
R
,
U
, or
D
.
Input
Input is given from Standard Input in the following format:
S
Output
Print
Yes
if
S
is easily playable, and
No
otherwise.
Sample Input 1
RUDLUDR
Sample Output 1
Yes
Every character in an odd position (
1
-st,
3
-rd,
5
-th,
7
-th) is
R
,
U
, or
D
.
Every character in an even position (
2
-nd,
4
-th,
6
-th) is
L
,
U
, or
D
.
Thus,
S
is easily playable.
Sample Input 2
DULL
Sample Output 2
No
The
3
-rd character is not
R
,
U
, nor
D
, so
S
is not easily playable.
Sample Input 3
UUUUUUUUUUUUUUU
Sample Output 3
Yes
Sample Input 4
ULURU
Sample Output 4
No
Sample Input 5
RDULULDURURLRDULRLR
Sample Output 5
Yes
Problem Description: Score: 300 points
Problem Statement
Takahashi has decided to hold fastest-finger-fast quiz games. Kizahashi, who is in charge of making the scoreboard, is struggling to write the program that manages the players' scores in a game, which proceeds as follows.
A game is played by
N
players, numbered
1
to
N
. At the beginning of a game, each player has
K
points.
When a player correctly answers a question, each of the other
N-1
players receives minus one (
-1
) point. There is no other factor that affects the players' scores.
At the end of a game, the players with
0
points or lower are eliminated, and the remaining players survive.
In the last game, the players gave a total of
Q
correct answers, the
i
-th of which was given by Player
A_i
.
For Kizahashi, write a program that determines whether each of the
N
players survived this game.
Constraints
All values in input are integers.
2 \leq N \leq 10^5
1 \leq K \leq 10^9
1 \leq Q \leq 10^5
1 \leq A_i \leq N\ (1 \leq i \leq Q)
Input
Input is given from Standard Input in the following format:
N
K
Q
A_1
A_2
.
.
.
A_Q
Output
Print
N
lines. The
i
-th line should contain
Yes
if Player
i
survived the game, and
No
otherwise.
Sample Input 1
6 3 4
3
1
3
2
Sample Output 1
No
No
Yes
No
No
No
In the beginning, the players' scores are
(3, 3, 3, 3, 3, 3)
.
Player
3
correctly answers a question. The players' scores are now
(2, 2, 3, 2, 2, 2)
.
Player
1
correctly answers a question. The players' scores are now
(2, 1, 2, 1, 1, 1)
.
Player
3
correctly answers a question. The players' scores are now
(1, 0, 2, 0, 0, 0)
.
Player
2
correctly answers a question. The players' scores are now
(0, 0, 1, -1, -1, -1)
.
Players
1, 2, 4, 5
and
6
, who have
0
points or lower, are eliminated, and Player
3
survives this game.
Sample Input 2
6 5 4
3
1
3
2
Sample Output 2
Yes
Yes
Yes
Yes
Yes
Yes
Sample Input 3
10 13 15
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9
Sample Output 3
No
No
No
No
Yes
No
No
No
Yes
No
Problem Description: Score : 400 points
Problem Statement
Takahashi is going to buy
N
items one by one.
The price of the
i
-th item he buys is
A_i
yen (the currency of Japan).
He has
M
discount tickets, and he can use any number of them when buying an item.
If
Y
tickets are used when buying an item priced
X
yen, he can get the item for
\frac{X}{2^Y}
(rounded down to the nearest integer) yen.
What is the minimum amount of money required to buy all the items?
Constraints
All values in input are integers.
1 \leq N, M \leq 10^5
1 \leq A_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N
M
A_1
A_2
...
A_N
Output
Print the minimum amount of money required to buy all the items.
Sample Input 1
3 3
2 13 8
Sample Output 1
9
We can buy all the items for
9
yen, as follows:
Buy the
1
-st item for
2
yen without tickets.
Buy the
2
-nd item for
3
yen with
2
tickets.
Buy the
3
-rd item for
4
yen with
1
ticket.
Sample Input 2
4 4
1 9 3 5
Sample Output 2
6
Sample Input 3
1 100000
1000000000
Sample Output 3
0
We can buy the item priced
1000000000
yen for
0
yen with
100000
tickets.
Sample Input 4
10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 4
9500000000
Problem Description: Score : 500 points
Problem Statement
Given is a string
S
of length
N
.
Find the maximum length of a non-empty string that occurs twice or more in
S
as contiguous substrings without overlapping.
More formally, find the maximum positive integer
len
such that there exist integers
l_1
and
l_2
(
1 \leq l_1, l_2 \leq N - len + 1
) that satisfy the following:
l_1 + len \leq l_2
S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)
If there is no such integer
len
, print
0
.
Constraints
2 \leq N \leq 5 \times 10^3
|S| = N
S
consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
N
S
Output
Print the maximum length of a non-empty string that occurs twice or more in
S
as contiguous substrings without overlapping. If there is no such non-empty string, print
0
instead.
Sample Input 1
5
ababa
Sample Output 1
2
The strings satisfying the conditions are:
a
,
b
,
ab
, and
ba
. The maximum length among them is
2
, which is the answer.
Note that
aba
occurs twice in
S
as contiguous substrings, but there is no pair of integers
l_1
and
l_2
mentioned in the statement such that
l_1 + len \leq l_2
.
Sample Input 2
2
xy
Sample Output 2
0
No non-empty string satisfies the conditions.
Sample Input 3
13
strangeorange
Sample Output 3
5
Problem Description: Score: 600 points
Problem Statement
We have
N
non-negative integers:
A_1, A_2, ..., A_N
.
Consider painting at least one and at most
N-1
integers among them in red, and painting the rest in blue.
Let the
beauty
of the painting be the
\mbox{XOR}
of the integers painted in red, plus the
\mbox{XOR}
of the integers painted in blue.
Find the maximum possible beauty of the painting.
What is
\mbox{XOR}
?
The bitwise
\mbox{XOR}
x_1 \oplus x_2 \oplus \ldots \oplus x_n
of
n
non-negative integers
x_1, x_2, \ldots, x_n
is defined as follows:
When
x_1 \oplus x_2 \oplus \ldots \oplus x_n
is written in base two, the digit in the
2^k
's place (
k \geq 0
) is
1
if the number of integers among
x_1, x_2, \ldots, x_n
whose binary representations have
1
in the
2^k
's place is odd, and
0
if that count is even.
For example,
3 \oplus 5 = 6
.
Constraints
All values in input are integers.
2 \leq N \leq 10^5
0 \leq A_i < 2^{60}\ (1 \leq i \leq N)
Input
Input is given from Standard Input in the following format:
N
A_1
A_2
...
A_N
Output
Print the maximum possible beauty of the painting.
Sample Input 1
3
3 6 5
Sample Output 1
12
If we paint
3
,
6
,
5
in blue, red, blue, respectively, the beauty will be
(6) + (3 \oplus 5) = 12
.
There is no way to paint the integers resulting in greater beauty than
12
, so the answer is
12
.
Sample Input 2
4
23 36 66 65
Sample Output 2
188
Sample Input 3
20
1008288677408720767 539403903321871999 1044301017184589821 215886900497862655 504277496111605629 972104334925272829 792625803473366909 972333547668684797 467386965442856573 755861732751878143 1151846447448561405 467257771752201853 683930041385277311 432010719984459389 319104378117934975 611451291444233983 647509226592964607 251832107792119421 827811265410084479 864032478037725181
Sample Output 3
2012721721873704572
A_i
and the answer may not fit into a
32
-bit integer type.
Problem Description: Score : 100 points
Problem Statement
Takahashi is going to set a
3
-character password.
How many possible passwords are there if each of its characters must be a digit between
1
and
N
(inclusive)?
Constraints
1 \leq N \leq 9
N
is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the number of possible passwords.
Sample Input 1
2
Sample Output 1
8
There are eight possible passwords:
111
,
112
,
121
,
122
,
211
,
212
,
221
, and
222
.
Sample Input 2
1
Sample Output 2
1
There is only one possible password if you can only use one kind of character.
Problem Description: Score : 200 points
Problem Statement
Takahashi went to an all-you-can-eat buffet with
N
kinds of dishes and ate all of them (Dish
1
, Dish
2
,
\ldots
, Dish
N
) once.
The
i
-th dish
(1 \leq i \leq N)
he ate was Dish
A_i
.
When he eats Dish
i
(1 \leq i \leq N)
, he gains
B_i
satisfaction points.
Additionally, when he eats Dish
i+1
just after eating Dish
i
(1 \leq i \leq N - 1)
, he gains
C_i
more satisfaction points.
Find the sum of the satisfaction points he gained.
Constraints
All values in input are integers.
2 \leq N \leq 20
1 \leq A_i \leq N
A_1, A_2, ..., A_N
are all different.
1 \leq B_i \leq 50
1 \leq C_i \leq 50
Input
Input is given from Standard Input in the following format:
N
A_1
A_2
...
A_N
B_1
B_2
...
B_N
C_1
C_2
...
C_{N-1}
Output
Print the sum of the satisfaction points Takahashi gained, as an integer.
Sample Input 1
3
3 1 2
2 5 4
3 6
Sample Output 1
14
Takahashi gained
14
satisfaction points in total, as follows:
First, he ate Dish
3
and gained
4
satisfaction points.
Next, he ate Dish
1
and gained
2
satisfaction points.
Lastly, he ate Dish
2
and gained
5 + 3 = 8
satisfaction points.
Sample Input 2
4
2 3 4 1
13 5 8 24
45 9 15
Sample Output 2
74
Sample Input 3
2
1 2
50 50
50
Sample Output 3
150
Problem Description: Score : 300 points
Problem Statement
There is an integer sequence
A
of length
N
whose values are unknown.
Given is an integer sequence
B
of length
N-1
which is known to satisfy the following:
B_i \geq \max(A_i, A_{i+1})
Find the maximum possible sum of the elements of
A
.
Constraints
All values in input are integers.
2 \leq N \leq 100
0 \leq B_i \leq 10^5
Input
Input is given from Standard Input in the following format:
N
B_1
B_2
...
B_{N-1}
Output
Print the maximum possible sum of the elements of
A
.
Sample Input 1
3
2 5
Sample Output 1
9
A
can be, for example, (
2
,
1
,
5
), (
-1
,
-2
,
-3
), or (
2
,
2
,
5
). Among those candidates,
A
= (
2
,
2
,
5
) has the maximum possible sum.
Sample Input 2
2
3
Sample Output 2
6
Sample Input 3
6
0 153 10 10 23
Sample Output 3
53
Problem Description: Score : 400 points
Problem Statement
There are
N
people standing in a queue from west to east.
Given is a string
S
of length
N
representing the directions of the people.
The
i
-th person from the west is facing west if the
i
-th character of
S
is
L
, and east if that character of
S
is
R
.
A person is happy if the person in front of him/her is facing the same direction.
If no person is standing in front of a person, however, he/she is not happy.
You can perform the following operation any number of times between
0
and
K
(inclusive):
Operation: Choose integers
l
and
r
such that
1 \leq l \leq r \leq N
, and rotate by
180
degrees the part of the queue: the
l
-th,
(l+1)
-th,
...
,
r
-th persons. That is, for each
i = 0, 1, ..., r-l
, the
(l + i)
-th person from the west will stand the
(r - i)
-th from the west after the operation, facing east if he/she is facing west now, and vice versa.
What is the maximum possible number of happy people you can have?
Constraints
N
is an integer satisfying
1 \leq N \leq 10^5
.
K
is an integer satisfying
1 \leq K \leq 10^5
.
|S| = N
Each character of
S
is
L
or
R
.
Input
Input is given from Standard Input in the following format:
N
K
S
Output
Print the maximum possible number of happy people after at most
K
operations.
Sample Input 1
6 1
LRLRRL
Sample Output 1
3
If we choose
(l, r) = (2, 5)
, we have
LLLRLL
, where the
2
-nd,
3
-rd, and
6
-th persons from the west are happy.
Sample Input 2
13 3
LRRLRLRRLRLLR
Sample Output 2
9
Sample Input 3
10 1
LLLLLRRRRR
Sample Output 3
9
Sample Input 4
9 2
RRRLRLRLL
Sample Output 4
7
Problem Description: Score: 500 points
Problem Statement
Given is a permutation
P
of
\{1, 2, \ldots, N\}
.
For a pair
(L, R) (1 \le L \lt R \le N)
, let
X_{L, R}
be the second largest value among
P_L, P_{L+1}, \ldots, P_R
.
Find
\displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}
.
Constraints
2 \le N \le 10^5
1 \le P_i \le N
P_i \neq P_j
(i \neq j)
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
P_1
P_2
\ldots
P_N
Output
Print
\displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}
.
Sample Input 1
3
2 3 1
Sample Output 1
5
X_{1, 2} = 2, X_{1, 3} = 2
, and
X_{2, 3} = 1
, so the sum is
2 + 2 + 1 = 5
.
Sample Input 2
5
1 2 3 4 5
Sample Output 2
30
Sample Input 3
8
8 2 7 3 4 5 6 1
Sample Output 3
136