1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Everyone Loves Tres
Contest: Codeforces Global Round 27
Difficulty rating: 900
Tags: constructive algorithms, greedy, math, number theory

Given a positive integer $$$n$$$. Find the smallest integer whose decimal representation has length $$$n$$$ and consists only of $$$3$$$s and $$$6$$$s such that it is divisible by both $$$33$$$ and $$$66$$$. If no such integer exists, print $$$-1$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1\le t\le 500$$$) — the number of test cases.

The only line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 500$$$) — the length of the decimal representation.

Output format:
For each test case, output the smallest required integer if such an integer exists and $$$-1$$$ otherwise.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For $$$n=1$$$, no such integer exists as neither $$$3$$$ nor $$$6$$$ is divisible by $$$33$$$.

For $$$n=2$$$, $$$66$$$ consists only of $$$6$$$s and it is divisible by both $$$33$$$ and $$$66$$$.

For $$$n=3$$$, no such integer exists. Only $$$363$$$ is divisible by $$$33$$$, but it is not divisible by $$$66$$$.

For $$$n=4$$$, $$$3366$$$ and $$$6666$$$ are divisible by both $$$33$$$ and $$$66$$$, and $$$3366$$$ is the smallest.

Example input:
6
1
2
3
4
5
7

Example output:
-1
66
-1
3366
36366
3336366

Editorial:
If we had the lexicographically smallest number for some $$$n$$$, we could extend it to the lexicographically smallest number for $$$n+2$$$ by prepending $$$33$$$ to it. This is due to the lexicographic condition that values minimize some digits over all the digits behind them. In other words, $$$3666xx$$$ is always better than $$$6333xx$$$.
We can observe that $$$66$$$ is the lexicographically smallest number for $$$n = 2$$$, $$$n = 1$$$ and $$$n = 3$$$ are impossible, and $$$36366$$$ is the lexicographically smallest number for $$$n = 5$$$.
So our final answer is $$$n-2$$$ $$$3$$$'s followed by $$$66$$$ if $$$n$$$ is even, $$$-1$$$ if $$$n = 1$$$ or $$$n = 3$$$, or $$$n-5$$$ $$$3$$$'s followed by $$$36366$$$ if $$$n$$$ is odd and greater than or equal to $$$5$$$.
For instance, for $$$n = 8$$$, the answer is $$$33333366$$$, and for $$$n = 9$$$, the answer is $$$333336366$$$.
Yet Another Real Number Problem
Contest: Codeforces Global Round 27
Difficulty rating: 1800
Tags: binary search, data structures, divide and conquer, greedy, implementation, math

You are given an array $$$b$$$ of length $$$m$$$. You can perform the following operation any number of times (possibly zero):

- Choose two distinct indices $$$i$$$ and $$$j$$$ where $$$\bf{1\le i < j\le m}$$$ and $$$b_i$$$ is even, divide $$$b_i$$$ by $$$2$$$ and multiply $$$b_j$$$ by $$$2$$$.

Since this problem is too easy, you are given an array $$$a$$$ of length $$$n$$$ and need to solve the problem for each prefix of $$$a$$$.

In other words, denoting the maximum sum of $$$b$$$ after performing any number of such operations as $$$f(b)$$$, you need to output $$$f([a_1])$$$, $$$f([a_1,a_2])$$$, $$$\ldots$$$, $$$f([a_1,a_2,\ldots,a_n])$$$ modulo $$$10^9+7$$$ respectively.

Input format:
The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the starting values of array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output $$$n$$$ integers representing the answer for each prefix of $$$a$$$ modulo $$$10^9+7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For each prefix in the first example, a possible array after operations is:

- $$$[1]$$$ and the sum is $$$1$$$;
- $$$[1, 2]$$$ and the sum is $$$3$$$;
- $$$[1, 1, 6]$$$ and the sum is $$$8$$$;
- $$$[1, 1, 3, 8]$$$ and the sum is $$$13$$$;
- $$$[1, 1, 3, 1, 40]$$$ and the sum is $$$46$$$;
- $$$[1, 1, 3, 1, 5, 48]$$$ and the sum is $$$59$$$;
- $$$[1, 1, 3, 1, 5, 3, 112]$$$ and the sum is $$$126$$$;
- $$$[1, 1, 3, 1, 5, 3, 7, 128]$$$ and the sum is $$$149$$$;
- $$$[1, 1, 3, 1, 5, 3, 7, 1, 1152]$$$ and the sum is $$$1174$$$;
- $$$[1, 1, 3, 1, 5, 3, 7, 1, 9, 1280]$$$ and the sum is $$$1311$$$.

Example input:
3
10
1 2 3 4 5 6 7 8 9 10
11
1 6 9 4 7 4 4 10 3 2 3
4
527792568 502211460 850237282 374773208

Example output:
1 3 8 13 46 59 126 149 1174 1311 
1 7 22 26 70 74 150 1303 1306 1308 1568 
527792568 83665723 399119771 773892979

Editorial:
Consider how to solve the problem for an entire array. We iterate backwards on the array, and for each $$$a_i$$$ we consider, we give all of its $$$2$$$ divisors to the largest $$$a_j > a_i$$$ with $$$j > i$$$. If $$$a_i$$$ is the largest, we do nothing.
To do this for every prefix $$$x$$$, notice that if we after we have iterated backwards from $$$x$$$ over $$$31$$$ $$$2$$$ divisors, the largest $$$a_i$$$ will always be larger than $$$10^9$$$ and thus all remaining $$$2$$$'s will be given to that largest $$$a_i$$$. Thus, we can iterate over these $$$31$$$ $$$2$$$'s and assign them manually, then multiply the largest $$$a_i$$$ by the number of $$$2$$$'s we have remaining. Thus, if we maintain the previous $$$31$$$ even numbers for every prefix, we can solve the problem in $$$O(n \log a_i)$$$.
Question Marks
Contest: Codeforces Round 963 (Div. 2)
Difficulty rating: 800
Tags: greedy, implementation

Tim is doing a test consisting of $$$4n$$$ questions; each question has $$$4$$$ options: 'A', 'B', 'C', and 'D'. For each option, there are exactly $$$n$$$ correct answers corresponding to that option — meaning there are $$$n$$$ questions with the answer 'A', $$$n$$$ questions with the answer 'B', $$$n$$$ questions with the answer 'C', and $$$n$$$ questions with the answer 'D'.

For each question, Tim wrote his answer on the answer sheet. If he could not figure out the answer, he would leave a question mark '?' for that question.

You are given his answer sheet of $$$4n$$$ characters. What is the maximum number of correct answers Tim can get?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 100$$$).

The second line of each test case contains a string $$$s$$$ of $$$4n$$$ characters ($$$s_i \in \{\texttt{A}, \texttt{B}, \texttt{C}, \texttt{D}, \texttt{?}\}$$$) — Tim's answers for the questions.

Output format:
For each test case, print a single integer — the maximum score that Tim can achieve.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, there is exactly one question with each answer 'A', 'B', 'C', and 'D'; so it's possible that Tim gets all his answers correct.

In the second test case, there are only two correct answers 'A' which makes him get exactly $$$2$$$ points in any case.

In the third test case, Tim can get at most $$$2$$$ correct answers with option 'A' and $$$2$$$ correct answers with option 'B'. For example, he would get $$$4$$$ points if the answers were 'AACCBBDD'.

In the fourth test case, he refuses to answer any question at all, which makes him get $$$0$$$ points.

Example input:
6
1
ABCD
2
AAAAAAAA
2
AAAABBBB
2
????????
3
ABCABCABCABC
5
ACADC??ACAC?DCAABC?C

Example output:
4
2
4
0
9
13

Editorial:
Parity and Sum
Contest: Codeforces Round 963 (Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, greedy

Given an array $$$a$$$ of $$$n$$$ positive integers.

In one operation, you can pick any pair of indexes $$$(i, j)$$$ such that $$$a_i$$$ and $$$a_j$$$ have distinct parity, then replace the smaller one with the sum of them. More formally:

- If $$$a_i < a_j$$$, replace $$$a_i$$$ with $$$a_i + a_j$$$;
- Otherwise, replace $$$a_j$$$ with $$$a_i + a_j$$$.

Find the minimum number of operations needed to make all elements of the array have the same parity.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the minimum number of operations required.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, all integers already have the same parity. Therefore, no operation is needed.

In the third test case, we can perform two operations $$$(1, 2)$$$ and $$$(1, 3)$$$. The array $$$a$$$ transforms as follows: $$$a = [\color{red}2, \color{red}3, 4] \longrightarrow [\color{red}5, 3, \color{red}4] \longrightarrow [5, 3, 9]$$$.

In the fourth test case, an example of an optimal sequence of operations is $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(1, 4)$$$, and $$$(1, 4)$$$. The array $$$a$$$ transforms as follows: $$$a = [\color{red}3, \color{red}2, 2, 8] \longrightarrow [\color{red}3, 5, \color{red}2, 8] \longrightarrow [\color{red}3, 5, 5, \color{red}8] \longrightarrow [\color{red}{11}, 5, 5, \color{red}8] \longrightarrow [11, 5, 5, 19]$$$.

Example input:
7
5
1 3 5 7 9
4
4 4 4 4
3
2 3 4
4
3 2 2 8
6
4 3 6 1 2 1
6
3 6 1 2 1 2
5
999999996 999999997 999999998 999999999 1000000000

Example output:
0
0
2
4
3
3
3

Editorial:
Light Switches
Contest: Codeforces Round 963 (Div. 2)
Difficulty rating: 1400
Tags: implementation, math

There is an apartment consisting of $$$n$$$ rooms, each with its light initially turned off.

To control the lights in these rooms, the owner of the apartment decided to install chips in the rooms so that each room has exactly one chip, and the chips are installed at different times. Specifically, these times are represented by the array $$$a_1, a_2, \ldots, a_n$$$, where $$$a_i$$$ is the time (in minutes) at which a chip is installed in the $$$i$$$-th room.

As soon as a chip is installed, it changes the room's light status every $$$k$$$ minutes — it turns on the light for $$$k$$$ minutes, then turns it off for the next $$$k$$$ minutes, then turns it back on for the next $$$k$$$ minutes, and so on. In other words, the light status is changed by the chip at minute $$$a_i$$$, $$$a_i + k$$$, $$$a_i + 2k$$$, $$$a_i + 3k$$$, $$$\ldots$$$ for the $$$i$$$-th room.

What is the earliest moment when all rooms in the apartment have their lights turned on?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — the number of rooms in the apartment and the period of the chips.

The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the moments when the chips are installed.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print a single integer — the answer to the question (in minutes). If there is no such moment that the lights are turned on in all the rooms, print $$$-1$$$ instead.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, all lights will be on by the minute $$$5$$$ without any of them being turned off by the chips. The answer is $$$5$$$.

In the second test case, due to $$$k=3$$$, the $$$1$$$-st light will be on at minutes $$$2, 3, 4, 8, 9, 10, 14, \ldots$$$; meanwhile, the $$$4$$$-th light will be on at minutes $$$5, 6, 7, 11, 12, 13, 17, \ldots$$$. These two sequences don't have any number in common, so they will never be on at the same time.

In the third test case, it can be seen that the $$$1$$$-st and $$$2$$$-nd lights will be turned off at minutes $$$6$$$ and $$$7$$$, but the chips will turn them back on at minutes $$$9$$$ and $$$10$$$. The $$$3$$$-rd and $$$4$$$-th lights will also be on at minute $$$10$$$, so the answer is $$$10$$$.

Example input:
9
4 4
2 3 4 5
4 3
2 3 4 5
4 3
3 4 8 9
3 3
6 2 1
1 1
1
7 5
14 34 6 25 46 7 17
6 5
40 80 99 60 90 50
6 5
64 40 50 68 70 10
2 1
1 1000000000

Example output:
5
-1
10
8
1
47
100
-1
-1

Editorial:
Med-imize
Contest: Codeforces Round 963 (Div. 2)
Difficulty rating: 2200
Tags: binary search, dp, greedy

Given two positive integers $$$n$$$ and $$$k$$$, and another array $$$a$$$ of $$$n$$$ integers.

In one operation, you can select any subarray of size $$$k$$$ of $$$a$$$, then remove it from the array without changing the order of other elements. More formally, let $$$(l, r)$$$ be an operation on subarray $$$a_l, a_{l+1}, \ldots, a_r$$$ such that $$$r-l+1=k$$$, then performing this operation means replacing $$$a$$$ with $$$[a_1, \ldots, a_{l-1}, a_{r+1}, \ldots, a_n]$$$.

For example, if $$$a=[1,2,3,4,5]$$$ and we perform operation $$$(3,5)$$$ on this array, it will become $$$a=[1,2]$$$. Moreover, operation $$$(2, 4)$$$ results in $$$a=[1,5]$$$, and operation $$$(1,3)$$$ results in $$$a=[4,5]$$$.

You have to repeat the operation while the length of $$$a$$$ is greater than $$$k$$$ (which means $$$|a| \gt k$$$). What is the largest possible median$$$^\dagger$$$ of all remaining elements of the array $$$a$$$ after the process?

$$$^\dagger$$$The median of an array of length $$$n$$$ is the element whose index is $$$\left \lfloor (n+1)/2 \right \rfloor$$$ after we sort the elements in non-decreasing order. For example: $$$median([2,1,5,4,3]) = 3$$$, $$$median([5]) = 5$$$, and $$$median([6,8,2,4]) = 4$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 5 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output format:
For each test case, print a single integer — the largest median possible after performing the operations.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, you can select a subarray $$$(l, r)$$$ which can be either $$$(1, 3)$$$ or $$$(2, 4)$$$. Thus, two obtainable final arrays are $$$[3]$$$ and $$$[2]$$$. The former one has the larger median ($$$3 > 2$$$) so the answer is $$$3$$$.

In the second test case, three obtainable final arrays are $$$[6, 4]$$$, $$$[3, 4]$$$, and $$$[3, 2]$$$. Their medians are $$$4$$$, $$$3$$$, and $$$2$$$ respectively. The answer is $$$4$$$.

In the third test case, only one element is left in the final array and it can be any element of the initial array. The largest one among them is $$$9$$$, so the answer is $$$9$$$.

Example input:
5
4 3
3 9 9 2
5 3
3 2 5 6 4
7 1
5 9 2 6 5 4 6
8 2
7 1 2 6 8 3 4 5
4 5
3 4 5 6

Example output:
3
4
9
6
4

Editorial:
Dyn-scripted Robot (Easy Version)
Contest: Codeforces Round 963 (Div. 2)
Difficulty rating: 2400
Tags: brute force, chinese remainder theorem, constructive algorithms, math, number theory

This is the easy version of the problem. The only difference is that in this version $$$k \le n$$$. You can make hacks only if both versions of the problem are solved.

Given a $$$w \times h$$$ rectangle on the $$$Oxy$$$ plane, with points $$$(0, 0)$$$ at the bottom-left and $$$(w, h)$$$ at the top-right of the rectangle.

You also have a robot initially at point $$$(0, 0)$$$ and a script $$$s$$$ of $$$n$$$ characters. Each character is either L, R, U, or D, which tells the robot to move left, right, up, or down respectively.

The robot can only move inside the rectangle; otherwise, it will change the script $$$s$$$ as follows:

- If it tries to move outside a vertical border, it changes all L characters to R's (and vice versa, all R's to L's).
- If it tries to move outside a horizontal border, it changes all U characters to D's (and vice versa, all D's to U's).

Then, it will execute the changed script starting from the character which it couldn't execute.

An example of the robot's movement process, $$$s = \texttt{"ULULURD"}$$$

The script $$$s$$$ will be executed for $$$k$$$ times continuously. All changes to the string $$$s$$$ will be retained even when it is repeated. During this process, how many times will the robot move to the point $$$(0, 0)$$$ in total? Note that the initial position does NOT count.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains four integers $$$n$$$, $$$k$$$, $$$w$$$, and $$$h$$$ ($$$1 \le n, w, h \le 10^6$$$; $$$1 \le k \le n$$$).

The second line contains a single string $$$s$$$ of size $$$n$$$ ($$$s_i \in \{\texttt{L}, \texttt{R}, \texttt{U}, \texttt{D}\}$$$) — the script to be executed.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, print a single integer — the number of times the robot reaches $$$(0, 0)$$$ when executing script $$$s$$$ for $$$k$$$ times continuously.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the robot only moves up and right. In the end, it occupies the position $$$(2, 2)$$$ but never visits $$$(0, 0)$$$. So the answer is $$$0$$$.

In the second test case, each time executing the script the robot visits the origin twice. And since $$$k=2$$$, it visits the origin $$$2 \cdot 2 = 4$$$ times overall.

In the third test case, the visualization is shown as below:

Example input:
5
2 2 2 2
UR
4 2 1 1
LLDD
6 3 3 1
RLRRRL
5 5 3 3
RUURD
7 5 3 4
RRDLUUU

Example output:
0
4
3
0
1

Editorial:
Dyn-scripted Robot (Hard Version)
Contest: Codeforces Round 963 (Div. 2)
Difficulty rating: 2800
Tags: chinese remainder theorem, math, number theory

This is the hard version of the problem. The only difference is that in this version $$$k \le 10^{12}$$$. You can make hacks only if both versions of the problem are solved.

Given a $$$w \times h$$$ rectangle on the $$$Oxy$$$ plane, with points $$$(0, 0)$$$ at the bottom-left and $$$(w, h)$$$ at the top-right of the rectangle.

You also have a robot initially at point $$$(0, 0)$$$ and a script $$$s$$$ of $$$n$$$ characters. Each character is either L, R, U, or D, which tells the robot to move left, right, up, or down respectively.

The robot can only move inside the rectangle; otherwise, it will change the script $$$s$$$ as follows:

- If it tries to move outside a vertical border, it changes all L characters to R's (and vice versa, all R's to L's).
- If it tries to move outside a horizontal border, it changes all U characters to D's (and vice versa, all D's to U's).

Then, it will execute the changed script starting from the character which it couldn't execute.

An example of the robot's movement process, $$$s = \texttt{"ULULURD"}$$$

The script $$$s$$$ will be executed for $$$k$$$ times continuously. All changes to the string $$$s$$$ will be retained even when it is repeated. During this process, how many times will the robot move to the point $$$(0, 0)$$$ in total? Note that the initial position does NOT count.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains four integers $$$n$$$, $$$k$$$, $$$w$$$, and $$$h$$$ ($$$1 \le n, w, h \le 10^6$$$; $$$1 \le k \le 10^{12}$$$).

The second line contains a single string $$$s$$$ of size $$$n$$$ ($$$s_i \in \{\texttt{L}, \texttt{R}, \texttt{U}, \texttt{D}\}$$$) — the script to be executed.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, print a single integer — the number of times the robot reaches $$$(0, 0)$$$ when executing script $$$s$$$ for $$$k$$$ times continuously.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the robot only moves up and right for the first two executions. After that, it occupies the position $$$(2, 2)$$$. For the next two executions, it moves down and left and finishes at $$$(0, 0)$$$. So the answer is $$$1$$$.

In the second test case, each time executing the script the robot visits the origin twice. And since $$$k=2$$$, it visits the origin $$$2 \cdot 2 = 4$$$ times overall.

In the third test case, the visualization is shown as below:

Example input:
6
2 4 2 2
UR
4 2 1 1
LLDD
6 3 3 1
RLRRRL
5 6 3 3
RUURD
7 5 3 4
RRDLUUU
7 123456789999 3 2
ULULURD

Example output:
1
4
3
1
1
41152263332

Editorial:
The Bento Box Adventure
Contest: 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 1300
Tags: implementation, sortings

Image generated by ChatGPT 4o.

Boxed meals in Taiwan are very common, offering convenient and affordable nutrition-balanced choices for students and office workers. These meals typically include a variety of vegetables, protein, and rice, providing a well-rounded diet. With numerous options available at local self-service restaurants, they are a popular choice for those looking for a quick, healthy lunch.

There are five Taiwanese self-service restaurants numbered from 1 to 5. You plan to visit a different restaurant each day from Monday to Friday to pack a boxed meal for lunch. You've already visited one restaurant from Monday to Thursday, each time visiting a different one. Now, it's Friday, and you want to visit the last remaining restaurant that you haven't been to yet this week.

Write a program that takes as input the four restaurants you've already visited (one for each day from Monday to Thursday) and outputs the restaurant you should visit on Friday.

Input format:
A single line of input containing four integers $$$a, b, c, d$$$, each between 1 and 5 (inclusive), representing the restaurant numbers you visited from Monday to Thursday, in order.

- $$$1\le a, b, c, d\le 5$$$
- All four numbers will be different.

Output format:
Output the restaurant number you should visit on Friday.

Constraints:
Time limit: 1.0 s
Memory limit: 1024.0 MB

Example input:
1 3 2 5

Example output:
4

Example input:
2 5 4 3

Example output:
1

Editorial: