| Problem description | | Progress |
ID 32981.
Sale
Темы:
"Two Pointers"
Dictionaries
The store is having a New Year sale – prices of all goods are reduced by 25%. It turned out that initially all prices were divisible by 4, so after the price decrease, all prices are also expressed as an integer. In the evening before the sale, the merchandiser removed the price tags from all the goods and printed another price tag with a reduced price for each product. He left all the price tags on the table, hoping to hang them up in the morning. But when he came to the store in the morning, he found that the cleaning lady had mixed all the price tags together, and now he needs to separate the old price tags from the new ones.
Help him solve this problem.
Input
The first line of the input contains the total number of price tags N, 2 <= N <= 105, N – even number. The following N lines contain positive integers not exceeding 109, in non-decreasing order, one per line – numbers written on all price tags (both old and new). It is guaranteed that the input data is correct, that is, the solution exists.
Imprint
The program should output N/2 integers in non-decreasing order – the cost of goods after price reduction.
Examples
| # |
Input |
Output |
Note |
| 1 |
6
30
40
42
45
56
60
|
30
42
45
|
Before the sale, the prices of the goods were 40, 56, 60, after the price reduction
these products have become equal to 30, 42, 45.
|
| |
![]()
|
|
Темы:
"Two Pointers"
Given an array of N positive numbers. Find in it the minimum number of consecutive numbers such that their sum is greater than K.
Input
The first line contains the number N, the second - K (0<N<= 10 6, 0<=K<= 10 9). The third line contains the natural numbers of the sequence.
Imprint
Print the length of the smallest sequence of numbers whose sum is greater than K. If such a sequence is not found, then print -1.
Examples
| # |
Input |
Output |
| 1 |
6
7
3 1 3 2 4 3
| 3 |
| |
![]()
|
|
Темы:
"Two Pointers"
Students from one of the universities designed a robot to partially automate the process of assembling an aircraft engine.
In the process of assembling the engine, 26 types of operations can occur, which are indicated by lowercase letters of the Latin alphabet. The assembly process consists of N operations.
It is supposed to use the robot once to perform part of the consecutive operations from the assembly process.
The robot's memory consists of K cells, each containing one operation. Operations are executed sequentially, starting with the first, in the order in which they are located in memory. After completing the last one, the robot continues with the first one. The robot can be stopped after any operation. Using a robot is economically viable if it performs at least K + 1 operations.
You need to write a program that, given the assembly process, will determine the number of economically viable ways to use the robot.
Input
The first line contains the number K > 0 - the number of operations that can be written to the robot's memory.
The second line consists of N > K lowercase Latin letters denoting operations - engine assembly process. Operations of the same type are denoted by the same letter (N <= 200000).
Output
Print a single integer - the number of cost-effective ways to use the robot.
| Input |
Output |
|
2
zabacabab
|
5 |
2
abc |
0 |
| |
![]()
|
|
Темы:
"Two Pointers"
Binary search in an array
Uncle Fyodor, the cat Matroskin and Sharik decided to update the fence around their garden in Prostokvashino. Matroskin and Sharik, without thinking twice, dug N pillars along one of the sides of the site. This upset Uncle Fyodor very much, as his friends forgot about the most important — the gate had to be exactly on this side, and for it it was necessary to leave an opening with a width of at least W. Now they will have to dig out some posts.
To keep your work from going to waste, dig as few posts as possible. Help Uncle Fyodor determine which pillars to dig. After digging out the posts, there must be a gap (between the two remaining posts, or between the remaining post and the end of the side of the lot, or between the two ends of the side of the lot) of a width greater than or equal to W.
Input
The first line contains two integers N and W — the number of dug-in poles and the minimum required width of the opening for the gate, respectively. It is guaranteed that 0<=N<=30000 and that 0<=W<=60000.
We will assume that the coordinate axis is introduced along the side of the site that interests us. The second line of the input file contains two numbers L and R — coordinates of the left and right end of this side (LR). This is followed by N numbers — the coordinates of the dug-in pillars. All coordinates (including L and R) — different integers, modulo not exceeding 30000. It is guaranteed that all posts are dug between the left and right ends of the side.
Output
The first line of the output file should contain the minimum number of posts to be dug. The numbers of these pillars should follow. The columns are numbered in the order they are specified in the input file, starting from 1.
If there are multiple solutions, you can output any one. If there is no solution, then output one line containing the number -1 to the output file.
| Input |
Output |
|
3 2
2 6
3 4 5
|
1
2 |
|
3 2
16
4 3 5
|
0 |
|
3 5
1 7
5 3 4
|
3
2
1
3
|
| |
![]()
|
|
Темы:
"Two Pointers"
N tickets are sold at one of the Moscow railway stations. Each cash desk works without interruption for a certain period of time according to a fixed schedule (the same every day). It is required to determine how long during the day all cash desks work at the same time.
Input
First enter one integer N (0<N<=10000).
In each of the next N lines there are 6 space-separated integers, the first three of which indicate the opening time of the cash desk in hours, minutes and seconds (hours — integer from 0 to 23, minutes and seconds — integers from 0 up to 59), the remaining three — closing time in the same format. Numbers are separated by spaces.
The opening time means that the cashier is already open at the corresponding second, and the closing time — that at the corresponding second the cashier is no longer working. For example, a cash desk that is open from 10:30:30 to 10:35:30 is open for 300 seconds a day.
If the opening time coincides with the closing time, then the ticket office is open around the clock. If the first time is greater than the second, then the cash desk starts work before midnight, and ends — the next day.
Output
Required to output a single number — total time per day (in seconds) during which all N cash desks work.
| Input |
Output |
|
3
1 0 0 23 0 0
12 0 0 12 0 0
22 0 0 2 0 0
|
7200 |
|
2
9 30 0 14 0 0
14 15 0 21 0 0
|
0 |
|
2
14 0 0 18 0 0
10 0 0 14 0 1
|
1 |
| |
![]()
|
|
Темы:
"Two Pointers"
On the distant planet Tau Ceti there are customs that we do not understand. For example, it is very unusual for Taukitians to choose names for their children. The parents choose the name of the child in such a way that it can be obtained both by removing a certain set of letters from the father's name and by removing a certain set of letters from the mother's name. For example, if the father's name is "abacaba" and the mother's name is — "bbccaa", then their child may be named "a", "bba", "bcaa", but cannot be named "aaa", "ab" or "bbc". It is possible for a child's name to be the same as the name of the father and/or mother if it can be derived from the other parent's name by removing a few (possibly none) of the letters.
Have a father named X and a mother named Y choose a name for their newborn child. Since in Taukitian schools, students are often called to the board in the lexicographic order of the names of the students, that is, in the order of the names in the dictionary, they want to choose a name for their child so that it follows lexicographically as late as possible.
- Formally, the string S is lexicographically greater than the string T if one of two conditions is true: the string T is obtained from S by removing one or more letters from the end of the string S;
- the first (i - 1) characters of strings T and S do not differ, and the letter in the i-th position of the string T follows in the alphabet before the letter in the i-th position of the string S.
It is required to write a program that, given the names of the father and mother, finds the lexicographically largest name for their child.
Input
The first line of the input file contains X — father's name. The second line of the input file contains Y — mother's name. Each name consists of lowercase Latin letters, includes at least one letter, and is no longer than 105 letters.
Output
The output file must contain the lexicographically largest possible child name you are looking for. If there is no suitable name for the child, the output file must be empty.
| Input |
Output |
|
abcabca
abcda
|
ca |
|
ccba
accbaa
|
ccba |
| |
![]()
|
|
Темы:
"Two Pointers"
In the park of the city of Pittsburgh there is a wonderful alley consisting of N trees planted in one row, each of one of K varieties. With Pittsburgh hosting the Byteland Open Programming Championship, it was decided to build a huge arena to host the competition. So, according to this plan, the entire alley was to be cut down. However, the Ministry of Trees and Bushes opposed this decision and demanded that some of the trees be left alone. According to the new construction plan, all trees that will not be cut down should form one continuous segment, which is a sub-segment of the original one. Each of the K tree species needs to be preserved at least one copy. Your task is to find the segment of the smallest length that satisfies the specified restrictions.
Input
The first line of the input file contains two numbers N and K ( 1 ≤ N , K ≤ 250000 ). The second line of the input file contains N numbers (separated by spaces), the i -th number of the second line specifies the color of the i -th tree from the left in the alley. It is guaranteed that at least one tree of each color is present
Output
In the output file print two numbers, the coordinates of the left and right ends of the segment of the minimum length that satisfies the condition. If there are several optimal answers, print any one.
| Input |
Output |
|
5 3
1 2 1 3 2
|
2 4 |
|
6 4
2 4 2 3 3 1
|
2 6 |
| |
![]()
|
|
Темы:
"Two Pointers"
Carol Danvers, known as Captain Marvel, counters the Skrull fleet. Each of
Skrull ships have a certain amount of power expressed as a natural number.
Carol thinks she's so strong that she can not only disable the fleet, but also a little
have fun. After carefully studying the power of the ship, she decided that she would disable them
in the following order: each time Carol will attack the ship that was not attacked before,
whose power is the median of the power of the remaining ships.
Carol calculates the median of a series of numbers as follows:
• If the number of numbers in the row is odd, then the median — the number in the middle of the given series sorted in ascending order.
• If the number of numbers in a row is even, then the median of the row is:
– The smaller of the two numbers in the middle of the given series, sorted in ascending order, if the two middle numbers are different.
– Any of the two numbers in the middle of the given series, sorted in ascending order,
if two means are equal.
Help Captain Marvel figure out the order in which to attack the ships.
Input data format
The first line contains one natural number n — number of ships in the Skrull fleet (1 <= n <= 105).
The second line contains n natural numbers ai — power of i-th ship (1 <= ai <=109).
Output format
Print n numbers — the power of the ships in the order that Carol will attack them.
| Input |
Output |
|
3
8 3 19
|
8 3 19 |
|
4
4 2 2 1
|
2 2 1 4 |
| |
![]()
|
|
Темы:
"Two Pointers"
Prefix sums(minimums, ...)
Aksinya loves Gregory, but she is married to Stepan. She is unhappy with her husband, so the time she spends with him can be characterized by a negative indicator of Aksinya's happiness (\(a_i < 0\)), and the time that she spends with Gregory, a positive indicator of happiness (\(a_i > 0\)). It is known that Aksinya spends one day either with her husband or with her lover.
Find the maximum total happiness for L days in which Aksinya will spend no more than C days with her husband.
Input
The first line contains 3 numbers: N – number of days, L and C (\(1 <= L, C <= N <= 1 000 000\)).
The second line contains N numbers a_i (\(1 <= |a_i| <= 1,000,000 000\)).
Input
You want to display the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
5 3 3
1 -1 2 -2 3
| 3 |
| |
![]()
|
|
Темы:
"Two Pointers"
Vasya was treated to sweets, and he decided to share some of the sweets with his younger brother Petya. However, he wants to share the sweets not equally, but brotherly.
To do this, Vasya decided to play the next game with himself. He spread the sweets on the table into several piles, which he arranged in a row. If there are at least two heaps, then from the first and last heaps in this row, he chooses the one in which there are fewer sweets. Let there be B sweets in the smallest pile. Then he shifts B sweets from the first pile to the second, and also shifts B sweets from the last pile to the penultimate one. At the same time, of course, one of the piles (or even two, if the first and last piles of sweets were equally divided) becomes empty, and Vasya forgets about its existence. He repeats these operations until one or two piles remain on the table.
If there is one pile left, then Vasya will eat all the candies himself, and if two — then he will eat candies from the first pile himself, and give Petya from the second pile.
Write a program that, based on the initial distribution of sweets in piles, will determine how Vasya's game will end.
Input
The initial arrangement of piles of sweets will be described by K pairs of numbers Ai, Ni, which indicate that Ni piles of sweets are laid out in a row on the table, Ai chocolates in each.
In the input file, the number K is given first (1≤K≤105). Then comes K pairs of numbers Ai, Ni (1≤Ai≤100, 1≤Ni≤108). The total number of heaps will also not exceed 108.
Imprint
In the output file print first 1 or 2 — the number of candy piles that will remain at the end of the game. Then output one or two numbers — the number of sweets in the remaining piles.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
3
2 2
3 2
2 1
| 2
11 1
| Initially, the candies are placed in the following piles: 2 piles of 2 candies, two piles of 3 candies, and one of 2:
2 2 3 3 2
Further, 2 candies are transferred from 1 and 5 piles to 2 and 4, while the 1 and 5 piles become empty, i.e. only 3 piles remain on the table:
4 3 5
Now 4 candies are transferred from piles 1 and 3 to pile 2 and two piles remain on the table, the game ends with the result 11 1
|
| 2 |
1
17 |
1
7 |
Initially, we have 7 piles of 1 candy in each. After the first shift, the following configuration will be obtained:
2 1 1 1 1 2
After the second:
3 1 3
After the third one, there will be one pile with 7 candies. |
| 3 |
5
1 1
2 1
3 1
4 1
5 2 |
2
15 5 |
Initially there are 6 piles:
1 2 3 4 5 5
After the first shift we get:
3 3 4 6 4
After the second:
6 4 9 1
After the third:
5 5 10
Finally, we get:
15 5 |
| |
![]()
|
|
Темы:
"Two Pointers"
Prefix sums(minimums, ...)
Given a sequence of N numbers. All its continuous subsequences are considered, in which the number of negative numbers does not exceed C. Find among them a subsequence with the maximum sum, length L. In your answer, indicate the sum of the found subsequence.
Input
The first line contains 3 numbers: the number of numbers N (1 <= N <= 1 000 000), L and C< /code> (\(1 <= L, C <= N <= 1,000,000\)). Each of the following N lines contain one number, modulo not exceeding 1000.
An example of the organization of source data in the input file (for L = 3 and C = 3):
5 3 3
1
-1
2
-2
3
Several sequences can be selected in this set, but with a maximum sum of 3 it will be: 2+(-2)+3.
Answer(for С = 3 and L = 3): 3. ;
| |
![]()
|
|
Темы:
"Two Pointers"
Greedy Algorithm
Farmer John has discovered that it is easier to milk a cow if there is another cow nearby for moral support. So he wants to break M of his cows (M <= 109, M - even ) to M/2 par. He places each of these pairs in a separate stall, and all pairs of cows are milked at the same time.
Each cow gives a different amount of milk. If cows in a pair produce A and B liters of milk, then milking this pair requires A+B units of time.
Help the FD determine the minimum amount of time possible for the entire milking process, assuming cows are best paired.
Input
The first input line contains N (1 <= N <= 100000). Each of the following N lines contains two integers x and y indicating that the FD has x cows with milk production of y (1 <= y <= 109) liters. The sum of all x's is M- the total number of cows.
Output
Print the minimum amount of time it will take to milk all the cows, assuming they are optimally paired.
Examples
| # |
Input |
Output |
| 1 |
3
18
2 5
1 2
|
10 |
| |
![]()
|
|
Темы:
"Two Pointers"
Greedy Algorithm
Constructive
Tommy has a children's toy "sorter", with n pegs arranged in a row. There is now no more than one disk on each peg (that is, there is a disk on some peg, but on some it No). Tommy wants to rearrange the given disks on the pegs so that they form a non-decreasing sequence when viewed from left to right. That is, on each next peg, the number of disks must be no less than on the previous one. What is the minimum number of Tommy's disks that need to be shifted?
Please note that some pegs may be empty at the end of sorting. Some pegs may contain more than 1 disc.
Input
The program receives as input in the first line an integer n (1 <= n <= 105), the number of peg on "sorter". The next line contains n integers a1, a2, ... an – the presence of a disc on the corresponding peg (0 <= ai <= 1). the number 0 means that there is no disk on the ith peg, 1 – there is a disc.
Imprint
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
8
0 0 1 1 1 1 1 1
|
0
|
| 2 |
eleven
1 1 0 0 1 0 0 1 1 1 0
|
3
|
| |
![]()
|
|
Темы:
"Two Pointers"
Gleb loves shopping. Once he got the idea to choose a cap, T-shirt, pants and boots so as to look as stylish as possible in them. In Gleb's understanding, the style of clothes is the greater, the smaller the difference in the color of the elements of his clothes.
There are N1 caps, N2 T-shirts, N3 pants and N4 pairs of boots (1 ≤ Ni ≤ 100 000). For each item of clothing, its color is known (an integer from 1 to 100 000). Clothing set — it is one cap, jersey, pants and one pair of boots. Each set is characterized by the maximum difference between any two of its elements. Help Gleb choose the most stylish set, that is, the set with the minimum color difference.
Input
For each type of clothing i (i = 1, 2, 3, 4), first enter the number Ni of clothing items of this type, then in the next line — a sequence of Ni integers describing the colors of the elements. All four types are entered sequentially, starting with caps and ending with boots. All entered numbers are integers, positive and do not exceed 100 000.
Output
Print four integers — colors respectively for the cap, T-shirt, pants and boots, which Gleb must choose from those available in order to look the most stylish. If there are several answers, print any one.
| Input |
Output |
|
3
1 2 3
2
1 3
2
3 4
2
2 3
|
3 3 3 3 |
|
1
5
4
3 6 7 10
4
18 3 9 11
1
20
|
5 6 9 20 |
| |
![]()
|
|
Темы:
"Two Pointers"
One-Dimensional Arrays
Implementation task
Alice left a secret sequence a[1..n] for her father Professor Seleznev. In order not to hide it, she decided to write it in the most visible place, but in a different order of numbers. Professor Seleznev knows that Alice rewrote the secret sequence as follows:
- the first number on the left is the number
a1;
- the first number on the right is the number
a2;
- the second number from the left (after
a1) is the number a3;
- the second number from the right (that is, before the number
a2) is the number a4;
- all other numbers are written in the same way.
That is, if the secret sequence was a = [1, 2, 3, 4, 5, 6], then the professor would see the following sequence [1, 3, 5 , 6, 4, 2]. Professor Seleznev was in a great hurry and only managed to save the sequence he saw into the computer. Write a program that will show the professor the original secret sequence.
Input
The first line contains the size of the sequence n (1 <= n <= 300) written by Alice for her father. The second line contains n numbers ai (1 <= ai < ;= 109) - the sequence itself.
Imprint
Print the original sequence that Alice wrote out for her father.
Examples
| # |
Input |
Output |
| 1 |
6
1 3 5 6 4 2
|
1 2 3 4 5 6 |
| 2 |
1
23 |
23 |
| |
![]()
|
|
Темы:
"Two Pointers"
Binary search
Implementation task
Tommy loves to read. He took n books from the library (in the ith book ai pages, pages are numbered with < code>1). Tommy is very careful with books, so he wrapped each of them in a cover. But, since he did not have any transparent covers, he numbered the books from 1 to n and wrote the number on the cover of each book.
Tommy has been reading for m days in a row. He reads books strictly in order, starting with book number 1. Every day, he writes down on the board the total number of pages he has read so far.
For example, if Tommy took 2 books and, at the same time, there were 3 pages in the first book, and 5 pages in the second, then after reading 2 pages on the first day, and 4 pages on the second day, Tommy had on the board two numbers 2 and 6 would be written.
Tommy took a short break, and when he returned to reading, he realized that he had forgotten which book he was reading and which page he had stopped on. He also does not want to lose statistics, but wants to correct it by adding on what day which book he read and on which page he stopped. Help Tommy, by the numbers written on the board, to determine on what day what book he read and on what page he stopped.
Input
The program receives several lines as input. The first line contains two integers n and m (1 <= n, n <= 2·105) - the number of books Tommy borrowed from the library and the number of days that Tommy read books. The second line contains the sequence a1, a2, ... an (1 <= a1<= 1010), where ai equals the number of pages in the ith book. The third line contains the sequence d1, d2, ... dm (1 <= dj <= a 1 + a2 +...+ an), where dj equals the total number of pages read by Tommy by jth day. All dj are in in ascending order.
Output
Output m lines. In each line print two numbers - нbook number k (1 <= k <= n) and page number in this book s (1 <= s <= ak) that Tommy settled on for the current day.
Examples
| # |
Input |
Output |
| 1 |
3 6
10 15 12
1 9 12 13 15 17
| 1 1
19
2 2
23
25
27 |
| 2 |
2 3
5 10000000000
5 6 9999999999
| 1 5
2 1
29999999994 |
| |
![]()
|
|
Темы:
Using sort
Greedy Algorithm
Implementation task
Simple puzzles
"Two Pointers"
Little Misha has cubes, each of which has one English lowercase letter written on it. Yesterday he laid out the cubes in two rows. In the first row Misha has n cubes with letters, in the second - m cubes with letters. It so happened that in these two rows there are no matching letters. In other words, no letter is contained in both rows at the same time.
Today little Misha decided to continue playing with blocks. But now he takes any one cube from any row and makes a third row of them, always adding a cube to the end. Little Misha never takes more than k dice in a row from the same row. Misha stopped playing when he ran out of cubes in one row (in the first or in the second).
Dad, who was watching the game, noticed that playing in this way, Misha got the lexicographically smallest line. Using the known two strings, which are formed by reading the letters of the first and second rows and the number k determine the string that little Misha received.
The string x is lexicographically less than the string y only and only if one of the following conditions is true:
- x is a prefix of y, but x != y;
- in the first position, where x and y differ, in the string x there is a letter that is in the alphabet earlier than the corresponding letter y.
Input
The program receives several lines as input. The first line contains three numbers: n - the number of cubes in the first row, m - the number of cubes in the second row, k > is an integer(1 <= n, m, k <= 100). The second line contains a string a of length n - a string formed by reading the letters written on the cubes of the first row. In the third line - string b of length m - a string formed by reading the letters written on the cubes of the second row.
Imprint
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
6 4 2
aaaaaa
bbbb |
aabaabaa |
| |
![]()
|
|
Темы:
"Two Pointers"
Intersection of many
Since childhood, Maxim was a good musician and jack of all trades. Recently, he independently made a simple percussion musical instrument — triangle. He needs to know what the frequency of the sound his instrument is making.
Maxim has a professional music tuner with which you can play a note at a given frequency. Maxim acts as follows: he turns on notes with different frequencies on the tuner and for each note determines by ear whether it is closer or further to the sound emitted by the triangle than the previous note. Since Maxim's hearing is absolute, he always determines this absolutely correctly.
Maxim showed you a recording in which the sequence of frequencies set by him on the tuner is given, and about each note, starting from the second, — closer or further it is to the sound of the triangle than the previous note. It is known in advance that the sound frequency of the Maxim triangle is not less than 30 hertz and not more than 4000 hertz.
It is required to write a program that determines in what interval the frequency of the sound of a triangle can be.
Input
The first line of the input file contains the integer n — the number of notes played by Maxim using the tuner (2 ≤ n ≤ 1000). The next n lines contain Maxim's entries, and each line contains two components: a real number fi — the frequency set on the tuner, in hertz (30 ≤ fi ≤ 4000), and the word "closer" or the word "further" for every frequency except the first one.
The word "closer" means that the frequency of this note is closer to the frequency of the triangle than the frequency of the previous note, which is formally described by the relationship: |fi−ftriangle.| < |fi−1−ftriangle|
The word "further" means that the frequency of this note is further than the previous one.
If it turned out that the next note is as close to the sound of a triangle as the previous note, then Maxim could write down any of the two words mentioned above.
It is guaranteed that the results obtained by Maxim are consistent.
Imprint
In the output file, you need to output two space-separated real numbers — the smallest and the largest possible value of the sounding frequency of the triangle made by Maxim. Numbers must be printed with a precision of at least 10−6.
Examples
| # |
Input |
Output |
| 1 |
3
440
220 closer
300 further |
30.0 260.0 |
| 2 |
4
554
880 further
440 closer
622 closer |
531.0 660.0 |
| |
![]()
|
|
Темы:
Binary search by answer
Strings
"Two Pointers"
In this problem, you need to find the longest substring of the given string, such that each character occurs in it no more than k times.
Input
The first line contains two integers n and k (1 ≤ n ≤ 100000, 1 ≤ k ≤ n ) , where n – the number of characters in the string. The second line contains n characters – the given string, consisting only of lowercase Latin letters.
Imprint
In the output file print two numbers – the length of the searched substring and the number of its first character. If there are several solutions, print any one.
Examples
| # |
Input |
Output |
| 1 |
3 1
abb |
2 1 |
| 2 |
5 2
ababa |
4 1 |
| |
![]()
|
|
Темы:
"Two Pointers"
Luka often travels to programming camps. Fees last n days. Luka records the number of tasks solved on each day of the camp. Luka considers the camp "effective" if there is only one continuous non-zero span of days (from l to r) when the following conditions were met for the number of solved problems:
1 <= l <= r <= n;al = al+1 = al+2 =…=ar;l = 1 or al-1 > al;r = n or ar < ar+1;
Examples
Let the A array store information about the solution of problems for each day of training, then:
1) array A = [5, 3, 3, 2, 3, 3, 4] describes "efficient", according to Luke, fees (interval of 1 day l = r = 4 satisfies the condition);
2) array A = [2, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8] also describes «efficient " charges (interval l = 1, r = 3 satisfies the condition);
3) array A = [1, 2, 3, 4, 3, 2, 1] describes not "efficient" fees (there are two intervals that satisfy the condition l = r = 1 and l = r = 7).
Luca just got back from another programming camp and told you how many problems he solved every day. Determine if the fees returned by Luca are "effective" in his opinion.
Input
The first line contains a single integer n (1 <= n <= 2·105) &mdash ; array length. Second line n integers ai (1 <= ai <= 109) — the number of problems solved by Luca on the i-th day .
Imprint
Print YES if Luka's collection was effective, and NO otherwise.
Examples
| # |
Input |
Output |
| 1 |
7
5 3 3 2 3 3 4 |
YES |
| 2 |
11
2 2 2 3 4 4 5 6 7 7 8
YES |
|
| 3 |
7
1 2 3 4 3 2 1
NO |
|
| |
![]()
|