1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Radio Station
Contest: Codeforces Round 459 (Div. 2)
Difficulty rating: 900
Tags: implementation, strings

As the guys fried the radio station facilities, the school principal gave them tasks as a punishment. Dustin's task was to add comments to nginx configuration for school's website. The school has n servers. Each server has a name and an ip (names aren't necessarily unique, but ips are). Dustin knows the ip and name of each server. For simplicity, we'll assume that an nginx command is of form "command ip;" where command is a string consisting of English lowercase letter only, and ip is the ip of one of school servers.

Each ip is of form "a.b.c.d" where a, b, c and d are non-negative integers less than or equal to 255 (with no leading zeros). The nginx configuration file Dustin has to add comments to has m commands. Nobody ever memorizes the ips of servers, so to understand the configuration better, Dustin has to comment the name of server that the ip belongs to at the end of each line (after each command). More formally, if a line is "command ip;" Dustin has to replace it with "command ip; #name" where name is the name of the server with ip equal to ip.

Dustin doesn't know anything about nginx, so he panicked again and his friends asked you to do his task for him.

Input format:
The first line of input contains two integers n and m (1 ≤ n, m ≤ 1000).

The next n lines contain the names and ips of the servers. Each line contains a string name, name of the server and a string ip, ip of the server, separated by space (1 ≤ |name| ≤ 10, name only consists of English lowercase letters). It is guaranteed that all ip are distinct.

The next m lines contain the commands in the configuration file. Each line is of form "command ip;" (1 ≤ |command| ≤ 10, command only consists of English lowercase letters). It is guaranteed that ip belongs to one of the n school servers.

Output format:
Print m lines, the commands in the configuration file after Dustin did his task.

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

Example input:
2 2
main 192.168.0.2
replica 192.168.0.1
block 192.168.0.1;
proxy 192.168.0.2;

Example output:
block 192.168.0.1; #replica
proxy 192.168.0.2; #main

Example input:
3 5
google 8.8.8.8
codeforces 212.193.33.27
server 138.197.64.57
redirect 138.197.64.57;
block 8.8.8.8;
cf 212.193.33.27;
unblock 8.8.8.8;
check 138.197.64.57;

Example output:
redirect 138.197.64.57; #server
block 8.8.8.8; #google
cf 212.193.33.27; #codeforces
unblock 8.8.8.8; #google
check 138.197.64.57; #server

Editorial:
Save the names and ips of the servers. Then for each command find the server in $${\mathcal{O}}(n)$$ and print its name.
Total time complexity: $${\mathcal{O}}(nm)$$
Era
Contest: Codeforces Round 752 (Div. 2)
Difficulty rating: 800
Tags: greedy

Shohag has an integer sequence $$$a_1, a_2, \ldots, a_n$$$. He can perform the following operation any number of times (possibly, zero):

- Select any positive integer $$$k$$$ (it can be different in different operations).
- Choose any position in the sequence (possibly the beginning or end of the sequence, or in between any two elements) and insert $$$k$$$ into the sequence at this position.
- This way, the sequence $$$a$$$ changes, and the next operation is performed on this changed sequence.

For example, if $$$a=[3,3,4]$$$ and he selects $$$k = 2$$$, then after the operation he can obtain one of the sequences $$$[\underline{2},3,3,4]$$$, $$$[3,\underline{2},3,4]$$$, $$$[3,3,\underline{2},4]$$$, or $$$[3,3,4,\underline{2}]$$$.

Shohag wants this sequence to satisfy the following condition: for each $$$1 \le i \le |a|$$$, $$$a_i \le i$$$. Here, $$$|a|$$$ denotes the size of $$$a$$$.

Help him to find the minimum number of operations that he has to perform to achieve this goal. We can show that under the constraints of the problem it's always possible to achieve this goal in a finite number of operations.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the initial length of the sequence.

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

Output format:
For each test case, print a single integer  — the minimum number of operations needed to perform to achieve the goal mentioned in the statement.

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

Note:
In the first test case, we have to perform at least one operation, as $$$a_2=3>2$$$. We can perform the operation $$$[1, 3, 4] \rightarrow [1, \underline{2}, 3, 4]$$$ (the newly inserted element is underlined), now the condition is satisfied.

In the second test case, Shohag can perform the following operations:

$$$[1, 2, 5, 7, 4] \rightarrow [1, 2, \underline{3}, 5, 7, 4] \rightarrow [1, 2, 3, \underline{4}, 5, 7, 4] \rightarrow [1, 2, 3, 4, 5, \underline{3}, 7, 4]$$$.

In the third test case, the sequence already satisfies the condition.

Example input:
4
3
1 3 4
5
1 2 5 7 4
1
1
3
69 6969 696969

Example output:
1
3
0
696966

Editorial:
If $$$a_i \gt i$$$ for some position $$$i$$$, then we need to insert at least $$$a_i - i$$$ new small elements before this position. Let $$$m = max(0, \max\limits_{i = 1}^{n}{(a_i - i)})$$$. So we need at least $$$m$$$ operations. But its not hard to see that $$$m$$$ operations are enough. For example, you can insert $$$m$$$ $$$1$$$s at the beginning of the sequence. This way, all elements will be shifted by $$$m$$$ positions, and consequently, will satisfy that $$$a_i \le i$$$ for each valid $$$i$$$.
Hot Bath
Contest: Codeforces Beta Round 93 (Div. 1 Only)
Difficulty rating: 1900
Tags: binary search, brute force, math

Bob is about to take a hot bath.

There are two taps to fill the bath: a hot water tap and a cold water tap. The cold water's temperature is t1, and the hot water's temperature is t2. The cold water tap can transmit any integer number of water units per second from 0 to x1, inclusive. Similarly, the hot water tap can transmit from 0 to x2 water units per second.

If y1 water units per second flow through the first tap and y2 water units per second flow through the second tap, then the resulting bath water temperature will be:

$$t = \frac{t_1 y_1 + t_2 y_2}{y_1 + y_2}$$

Bob wants to open both taps so that the bath water temperature was not less than t0. However, the temperature should be as close as possible to this value. If there are several optimal variants, Bob chooses the one that lets fill the bath in the quickest way possible.

Determine how much each tap should be opened so that Bob was pleased with the result in the end.

Input format:
You are given five integers t1, t2, x1, x2 and t0 (1 ≤ t1 ≤ t0 ≤ t2 ≤ 106, 1 ≤ x1, x2 ≤ 106).

Output format:
Print two space-separated integers y1 and y2 (0 ≤ y1 ≤ x1, 0 ≤ y2 ≤ x2).

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

Note:
In the second sample the hot water tap shouldn't be opened, but the cold water tap should be opened at full capacity in order to fill the bath in the quickest way possible.

Example input:
10 70 100 100 25

Example output:
99 33

Example input:
300 500 1000 1000 300

Example output:
1000 0

Editorial:
Password
Contest: Codeforces Beta Round 93 (Div. 1 Only)
Difficulty rating: 1700
Tags: binary search, dp, hashing, string suffix structures, strings

Asterix, Obelix and their temporary buddies Suffix and Prefix has finally found the Harmony temple. However, its doors were firmly locked and even Obelix had no luck opening them.

A little later they found a string s, carved on a rock below the temple's gates. Asterix supposed that that's the password that opens the temple and read the string aloud. However, nothing happened. Then Asterix supposed that a password is some substring t of the string s.

Prefix supposed that the substring t is the beginning of the string s; Suffix supposed that the substring t should be the end of the string s; and Obelix supposed that t should be located somewhere inside the string s, that is, t is neither its beginning, nor its end.

Asterix chose the substring t so as to please all his companions. Besides, from all acceptable variants Asterix chose the longest one (as Asterix loves long strings). When Asterix read the substring t aloud, the temple doors opened.

You know the string s. Find the substring t or determine that such substring does not exist and all that's been written above is just a nice legend.

Input format:
You are given the string s whose length can vary from 1 to 106 (inclusive), consisting of small Latin letters.

Output format:
Print the string t. If a suitable t string does not exist, then print "Just a legend" without the quotes.

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

Example input:
fixprefixsuffix

Example output:
fix

Example input:
abcdabc

Example output:
Just a legend

Editorial:
E-reader Display
Contest: Codeforces Beta Round 93 (Div. 1 Only)
Difficulty rating: 2000
Tags: constructive algorithms, greedy

After years of hard work scientists invented an absolutely new e-reader display. The new display has a larger resolution, consumes less energy and its production is cheaper. And besides, one can bend it. The only inconvenience is highly unusual management. For that very reason the developers decided to leave the e-readers' software to programmers.

The display is represented by n × n square of pixels, each of which can be either black or white. The display rows are numbered with integers from 1 to n upside down, the columns are numbered with integers from 1 to n from the left to the right. The display can perform commands like "x, y". When a traditional display fulfills such command, it simply inverts a color of (x, y), where x is the row number and y is the column number. But in our new display every pixel that belongs to at least one of the segments (x, x) - (x, y) and (y, y) - (x, y) (both ends of both segments are included) inverts a color.

For example, if initially a display 5 × 5 in size is absolutely white, then the sequence of commands (1, 4), (3, 5), (5, 1), (3, 3) leads to the following changes:

You are an e-reader software programmer and you should calculate minimal number of commands needed to display the picture. You can regard all display pixels as initially white.

Input format:
The first line contains number n (1 ≤ n ≤ 2000).

Next n lines contain n characters each: the description of the picture that needs to be shown. "0" represents the white color and "1" represents the black color.

Output format:
Print one integer z — the least number of commands needed to display the picture.

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

Example input:
5
01110
10010
10001
10011
11110

Example output:
4

Editorial:
Fibonacci Sums
Contest: Codeforces Beta Round 93 (Div. 1 Only)
Difficulty rating: 2300
Tags: dp, math

Fibonacci numbers have the following form:

F1 = 1,

F2 = 2,

Fi = Fi - 1 + Fi - 2, i > 2.

Let's consider some non-empty set S = {s1, s2, ..., sk}, consisting of different Fibonacci numbers. Let's find the sum of values of this set's elements:

$$\sum_{i=1}^{k}s_{i}=n$$

Let's call the set S a number n's decomposition into Fibonacci sum.

It's easy to see that several numbers have several decompositions into Fibonacci sum. For example, for 13 we have 13, 5 + 8, 2 + 3 + 8 — three decompositions, and for 16: 3 + 13, 1 + 2 + 13, 3 + 5 + 8, 1 + 2 + 5 + 8 — four decompositions.

By the given number n determine the number of its possible different decompositions into Fibonacci sum.

Input format:
The first line contains an integer t — the number of tests (1 ≤ t ≤ 105). Each of the following t lines contains one test.

Each test is an integer n (1 ≤ n ≤ 1018).

Please do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specificator.

Output format:
For each input data test print a single number on a single line — the answer to the problem.

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

Note:
Two decompositions are different if there exists a number that is contained in the first decomposition, but is not contained in the second one. Decompositions that differ only in the order of summands are considered equal.

Example input:
2
13
16

Example output:
3
4

Editorial:
Pills
Contest: Codeforces Beta Round 93 (Div. 1 Only)
Difficulty rating: 2900
Tags: brute force, flows

Doctor prescribed medicine to his patient. The medicine is represented by pills. Each pill consists of a shell and healing powder. The shell consists of two halves; each half has one of four colors — blue, red, white or yellow.

The doctor wants to put 28 pills in a rectangular box 7 × 8 in size. Besides, each pill occupies exactly two neighboring cells and any cell contains exactly one half of a pill. Thus, the result is a four colored picture 7 × 8 in size.

The doctor thinks that a patient will recover sooner if the picture made by the pills will be special. Unfortunately, putting the pills in the box so as to get the required picture is not a very easy task. That's why doctor asks you to help.

Doctor has some amount of pills of each of 10 painting types. They all contain the same medicine, that's why it doesn't matter which 28 of them will be stored inside the box.

Place the pills in the box so that the required picture was formed. If it is impossible to place the pills in the required manner, then place them so that the number of matching colors in all 56 cells in the final arrangement and the doctor's picture were maximum.

Input format:
First 7 lines contain the doctor's picture. Each line contains 8 characters, each character can be "B", "R", "W" and "Y" that stands for blue, red, white and yellow colors correspondingly.

Next four lines contain 10 numbers that stand for, correspondingly, the number of pills painted:

"BY" "BW" "BR" "BB"

"RY" "RW" "RR"

"WY" "WW"

"YY"

Those numbers lie within range from 0 to 28 inclusively. It is guaranteed that the total number of pills in no less than 28.

Output format:
Print on the first line the maximal number cells for which the colors match.

Then print 13 lines each containing 15 characters — the pills' position in the optimal arrangement. The intersections of odd lines and odd columns should contain characters "B", "R", "W" and "Y". All other positions should contain characters ".", "-" and "|". Use "-" and "|" to show which halves belong to one pill. See the samples for more clarification.

If there are several possible solutions, print any of them.

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

Example input:
WWWBBWWW
WWWBBWWW
YYWBBWWW
YYWBBWRR
YYWBBWRR
YYWBBWRR
YYWBBWRR
0 0 0 8
0 1 5
1 10
5

Example output:
53
W.W.W.B.B.W.W.W
|.|.|.|.|.|.|.|
W.W.W.B.B.W.W.W
...............
Y.Y.W.B.B.W.W-W
|.|.|.|.|.|....
Y.Y.W.B.B.W.R.R
............|.|
Y.Y.W.B.B.R.R.R
|.|.|.|.|.|....
Y.Y.W.B.B.W.R.R
............|.|
Y-Y.B-B.B-B.R.R

Example input:
WWWWWWWW
WBYWRBBY
BRYRBWYY
WWBRYWBB
BWWRWBYW
RBWRBWYY
WWWWWWWW
0 0 0 1
0 0 1
0 1
25

Example output:
15
W.Y.Y-Y.Y-Y.Y-Y
|.|............
W.Y.Y.Y.Y.B-B.Y
....|.|.|.....|
Y-Y.Y.Y.Y.Y-Y.Y
...............
Y.Y.Y.R.Y.Y.Y-Y
|.|.|.|.|.|....
Y.Y.Y.R.Y.Y.Y.Y
............|.|
Y-Y.Y.Y-Y.Y.Y.Y
....|.....|....
Y-Y.Y.Y-Y.Y.Y-Y

Editorial:
Medium Number
Contest: Codeforces Round 835 (Div. 4)
Difficulty rating: 800
Tags: implementation, sortings

Given three distinct integers $$$a$$$, $$$b$$$, and $$$c$$$, find the medium number between all of them.

The medium number is the number that is neither the minimum nor the maximum of the given three numbers.

For example, the median of $$$5,2,6$$$ is $$$5$$$, since the minimum is $$$2$$$ and the maximum is $$$6$$$.

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

The description of each test case consists of three distinct integers $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \leq a, b, c \leq 20$$$).

Output format:
For each test case, output a single integer — the medium number of the three numbers.

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

Example input:
9
5 2 6
14 3 4
20 2 1
1 2 3
11 19 12
10 8 20
6 20 3
4 1 3
19 8 4

Example output:
5
4
2
2
12
10
6
3
8

Editorial:
Here are two ways to implement what's given in the problem:
1. Take input as an array $$$[a_1, a_2, a_3]$$$, and sort it. Output the middle element.
2. Write two if-statements. The first: if $$$(a>b \text{ and } a<c) \text{ or } (a<b \text{ and } a>c)$$$, output $$$a$$$. Else, if $$$(b>a \text{ and } b<c) \text{ or } (b<a \text{ and } b>c)$$$, output $$$b$$$. Else, output $$$c$$$.
Atilla's Favorite Problem
Contest: Codeforces Round 835 (Div. 4)
Difficulty rating: 800
Tags: greedy, implementation, strings

In order to write a string, Atilla needs to first learn all letters that are contained in the string.

Atilla needs to write a message which can be represented as a string $$$s$$$. He asks you what is the minimum alphabet size required so that one can write this message.

The alphabet of size $$$x$$$ ($$$1 \leq x \leq 26$$$) contains only the first $$$x$$$ Latin letters. For example an alphabet of size $$$4$$$ contains only the characters $$$\texttt{a}$$$, $$$\texttt{b}$$$, $$$\texttt{c}$$$ and $$$\texttt{d}$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the length of the string.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting of lowercase Latin letters.

Output format:
For each test case, output a single integer — the minimum alphabet size required to so that Atilla can write his message $$$s$$$.

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

Note:
For the first test case, Atilla needs to know only the character $$$\texttt{a}$$$, so the alphabet of size $$$1$$$ which only contains $$$\texttt{a}$$$ is enough.

For the second test case, Atilla needs to know the characters $$$\texttt{d}$$$, $$$\texttt{o}$$$, $$$\texttt{w}$$$, $$$\texttt{n}$$$. The smallest alphabet size that contains all of them is $$$23$$$ (such alphabet can be represented as the string $$$\texttt{abcdefghijklmnopqrstuvw}$$$).

Example input:
5
1
a
4
down
10
codeforces
3
bcf
5
zzzzz

Example output:
1
23
19
6
26

Editorial:
To solve the problem we need to find the character with the highest alphabetical order in our string, since Atilla will need at least that alphabet size and won't need more. To do this iterate through the string and find the character with the highest alphabetical order. Output the maximum alphabetical order found. The solution can be done in $$$O(n).$$$
Advantage
Contest: Codeforces Round 835 (Div. 4)
Difficulty rating: 800
Tags: data structures, implementation, sortings

There are $$$n$$$ participants in a competition, participant $$$i$$$ having a strength of $$$s_i$$$.

Every participant wonders how much of an advantage they have over the other best participant. In other words, each participant $$$i$$$ wants to know the difference between $$$s_i$$$ and $$$s_j$$$, where $$$j$$$ is the strongest participant in the competition, not counting $$$i$$$ (a difference can be negative).

So, they ask you for your help! For each $$$i$$$ ($$$1 \leq i \leq n$$$) output the difference between $$$s_i$$$ and the maximum strength of any participant other than participant $$$i$$$.

Input format:
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2\cdot10^5$$$) — the length of the array.

The following line contains $$$n$$$ space-separated positive integers $$$s_1$$$, $$$s_2$$$, ..., $$$s_n$$$ ($$$1 \leq s_i \leq 10^9$$$) — the strengths of the participants.

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

Output format:
For each test case, output $$$n$$$ space-separated integers. For each $$$i$$$ ($$$1 \leq i \leq n$$$) output the difference between $$$s_i$$$ and the maximum strength of any other participant.

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

Note:
For the first test case:

- The first participant has a strength of $$$4$$$ and the largest strength of a participant different from the first one is $$$7$$$, so the answer for the first participant is $$$4 - 7 = -3$$$.
- The second participant has a strength of $$$7$$$ and the largest strength of a participant different from the second one is $$$5$$$, so the answer for the second participant is $$$7 - 5 = 2$$$.
- The third participant has a strength of $$$3$$$ and the largest strength of a participant different from the third one is $$$7$$$, so the answer for the third participant is $$$3 - 7 = -4$$$.
- The fourth participant has a strength of $$$5$$$ and the largest strength of a participant different from the fourth one is $$$7$$$, so the answer for the fourth participant is $$$5 - 7 = -2$$$.

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

Example output:
-3 2 -4 -2 
-1 1 
-4 -3 -2 -1 1 
-5 5 -5 
0 0 0 0

Editorial:
Make a copy of the array $$$s$$$: call it $$$t$$$. Sort $$$t$$$ in non-decreasing order, so that $$$t_1$$$ is the maximum strength and $$$t_2$$$ — the second maximum strength.
Then for everyone but the best person, they should compare with the best person who has strength $$$t_1$$$. So for all $$$i$$$ such that $$$s_i \neq t_1$$$, we should output $$$s_i - t_1$$$. Otherwise, output $$$s_i - t_2$$$ — the second highest strength, which is the next best person.
Challenging Valleys
Contest: Codeforces Round 835 (Div. 4)
Difficulty rating: 1000
Tags: implementation, two pointers

You are given an array $$$a[0 \dots n-1]$$$ of $$$n$$$ integers. This array is called a "valley" if there exists exactly one subarray $$$a[l \dots r]$$$ such that:

- $$$0 \le l \le r \le n-1$$$,
- $$$a_l = a_{l+1} = a_{l+2} = \dots = a_r$$$,
- $$$l = 0$$$ or $$$a_{l-1} > a_{l}$$$,
- $$$r = n-1$$$ or $$$a_r < a_{r+1}$$$.

Here are three examples:

The first image shows the array [$$$3, 2, 2, 1, 2, 2, 3$$$], it is a valley because only subarray with indices $$$l=r=3$$$ satisfies the condition.

The second image shows the array [$$$1, 1, 1, 2, 3, 3, 4, 5, 6, 6, 6$$$], it is a valley because only subarray with indices $$$l=0, r=2$$$ satisfies the codition.

The third image shows the array [$$$1, 2, 3, 4, 3, 2, 1$$$], it is not a valley because two subarrays $$$l=r=0$$$ and $$$l=r=6$$$ that satisfy the condition.

You are asked whether the given array is a valley or not.

Note that we consider the array to be indexed from $$$0$$$.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases is smaller than $$$2\cdot10^5$$$.

Output format:
For each test case, output "YES" (without quotes) if the array is a valley, and "NO" (without quotes) otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

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

Note:
The first three test cases are explained in the statement.

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

Example output:
YES
YES
NO
YES
YES
NO

Editorial:
One possible solution is to represent a range of equal element as a single element with that value. Construct this array $$$b$$$ and loop through it and check how many element $$$b_i$$$ satisfy the conditions $$$i = 0$$$ or $$$b_{i-1} < b_i$$$ and $$$i = n-1$$$ or $$$b_i > b_{i+1}$$$. If exactly one index satisfies these conditions, print "YES" and othewise "NO".
Complexity: $$$O(n)$$$