You are given an array of integers called a.
And you basically have you basically get to do the following operation for how many times that you want
to.
You can choose a subsegment starting from position L and ending in position.
Ah.
And the replay replace each and every element in that sub segment with the median of these Saberi.
This is what you can do, right.
Big ol L and R.
For example, if L and ah if that subarea was one four four six five its median is four.
So after performing this operation, each and every element here is four four one seven five eight is
five and so on and so forth.
Right.
So what we need to do is to tell Orac if it is possible or not, to convert all this array A into elements
of K.
So it consists only of elements equal to K by performing this operations.
If it's possible.
Print.
Yes.
If not print.
No.
That's all.
So yeah, this problem is not like a very hard core one in which you have to optimize it.
Right.
So it really doesn't ask like what is the minimal number of operations needed to transform this this
array in just to consist of values of key.
It really cares about whether it's possible or not.
So, yeah.
Cool.
All right.
Let's go and solve this.
So again, be prepared, because I'm gonna get you from my line of thought and how I felt about this
problem.
So the following thing struck to my mind.
I have this sabari or a rape.
I don't know why I keep seeing Savary.
But anyways, I always think about the let's say the negative part.
Right.
When I get these kind of problems, either if it's a yes or no problem or you get to tell the elsewhere
or know if there is not any answer or something like that, I always think about when there is no answer
at all.
So I started to think immediate the OK when there is not any answer there.
And the first thing that struck my mind and it's in the first example to.
Is that if you don't have any value key in that array.
Of course, you're not gonna have any answer, right?
If there is no value K, you won't have any Saberi that will have a median equal to K.
So you can't have all those elements to be equal to Kay.
So first observation, super simple.
If in your array there is not any value of K, then you print.
No.
Now what happens if we do have some values of K?
So this is code 46 for one.
And this is D, I think.
Right.
This is the call.
Let us see.
All right, great.
So what happens if there are some failures of.
Let's see here we have some key.
Great, and I started to think like this.
I have to use these values of cake in order to expand and make all the values in my array equal to cake.
So if this is a cake.
Let's take a look at its neighbors.
What are the options here?
Well, I could have either neighbors equal to Kay or neighbors less than Kay or neighbors greater than
Kay.
Right.
What if this right neighbor is less than key?
If I take this, too, this would be the median, right?
Okay, okay, so this means that if this is greater than Kay.
If I take this to Kate, is the media.
So, bam!
The next observation.
If I take a value of K and one of its neighbors is greater than K, I choose the sequence of these two
consecutive elements.
And when I perform an operation on them, guess what?
This is always going to be transformed into another game.
Let's say this was greater to.
Perfect.
Guess what, I I'm going to apply the operation on these neighbors.
So this is now going to be also equal to Kate.
Perfect.
Very nice.
So what happens is when I have some value of K.
As long as I have only neighbors greater than Kay.
I just perform.
These sequences of operations, first of all, this one.
And this is now also okay.
Right.
This is a key.
Then I perform this one.
Yes.
What?
This is a key.
Then I perform this one.
This is a key.
Then this one.
This is a key.
Right.
This is a key.
So all I can do is that if the key has neighbors of greater key on the right and neighbors.
Greater than key on the left.
I can extend and make all of those numbers equal.
Okay, cool.
So the real problem here.
I almost fall there.
The real problem here is that what happens when my neighbors are less than.
So let's suppose.
I have performed as many operations like this that I could.
K and Greater Neighbor.
Bam!
That neighbor risque and so on and so forth.
So what happens now is that I'm left with an array in which each neighbor of key is either a mother
value of key or someone less than key.
So basically there is like this k k k dad, that key.
And less than Kate, less than Kate, less than Kate, less than Kate.
Then again, k k that.
That Kate.
Less than Quiles, then, Kate.
Keiki and so on and so forth.
So after performing all those operations, this is what I'm left with.
All right.
Well, this is kind of impossible.
That's for sure.
I mean, it's not necessarily impossible.
By the way, when I thought about the problem, I thought this was impossible.
But it's not.
So stick with me.
I can take this to case.
And have them taken, we have this less element.
And guess what?
Because they have two values equal to Kay and one less than Kay.
The median is Kay.
So this element less than Kay is now.
Kay.
Let's say this is another element less than key.
I have read case.
If I have free gays and only one less than Ky, I can eat him basically.
And I want to transform him again into another cake.
And so on and so forth.
So what I figure now, which is really cool, is the following week.
Either if I have a value of key.
And something.
Greater than Kay.
I'm gonna convert this into K.K.
Or if I don't have any neighbor, which is greater than Kay.
So basically both of them are less.
Not both of them are less or equal.
Sorry.
So I have a kid.
If this was greater, I would have done this.
If this is less.
My only chance is to have another key here to back me up.
If this case can back me up here when I choose this.
So I am able to convert this into a KKK, right?
So the final solution is if I have a key and this is less.
And this is less.
No, I'm basically stuck because I don't have any case to back me up here.
If I did have a key here, that's great, because I can take this sequence right.
Or some key here, maybe this is also great because I can take this sequence.
But if I don't have those.
And let's say this is all so less and this is also less for is going to be quite hard, you know.
Right now I'm really kind of stuck because each and every Southbury that I choose from here is not gonna
convert me
all these values to key.
Let's say I have someone to save me here.
Some key here and maybe another one here.
Then everything's fine.
You know why?
Because I can choose this one.
Free case and two less, so the median is key.
And this one's R.K. to.
But even more important, I can choose this one.
I because they have two consecutive case.
But did you notice here, if I have a key and something greater than Kay, everything's fine.
I convert that into key.
If I have two consecutive case, everything's fine, I convert the first one just either to the right
or to the left into another key.
But if I have a KIA, we have two less than Kia.
The only thing that's gonna save me is that somewhere in the future, like here on the right, I'm gonna
have, again, two case that are that are consecutive or maybe.
These two weren't here, so I would have had less Leskie, less, less.
And some other lassies.
Some key here.
Maybe another less and some key here.
This is also going to save me because even if these two case are not consecutive, I can take three
consecutive positions.
Where two of them are kids.
And this is it.
This is all you need to have in this string.
If in this string, you have at least one.
Toppled one Saberi of free consecutive positions such that at least two of them are key or greater.
They could be greater, but not both of them.
Because if I have greater, greater, less than the median, is this greater, which is not OK.
I need at least one key and something greater than K, one K and something greater than K.
Right.
So what happens now is that.
I need to have at least one Saberi of free consecutive elements where two of them.
Are greater or equal than cake.
But as I've told you, this case could be a problem.
Well, it's not that big of a problem because even if I have this case and I choose to apply an operation
on this sub.
Eric.
It's gonna look like there's no greater greater great.
All right.
So now they are Rayder.
Let's say I had something less.
Oh, I can apply this again and I'm going to make this greater.
Then let's say I have some key here.
Ha, that's amazing.
I can take this, too.
And now this is K.K.
I can again take this, too.
And this is K.K and this is exactly the case that we have spoken in the beginning.
So the conclusion is the problem is a little bit tricky.
Like you really have to use your pen and paper or in my case, my pen and my graphic tablet.
You need to use the pen and paper.
And draw a lot of examples in order to figure out what happens when after seven examples drawn here.
We can't figure out.
That this problem has a solution.
If, first of all, there is at least.
One key.
There is at least so there exists some sequence.
I.
I plus one, I plus two.
There are at least.
Two elements, greater or equal than key.
And this is it.
You just need to check this two.
And as I've told you, if this doesn't hold, we have seen all the examples.
If this holds, everything's fine.
Let's say you have found this free and at least two of them are greater or equal than key.
Just like I've told you.
Let's take any example that you want.
Let's say I have two of them greater.
And one is less.
All right.
I applied on this free.
Now, this one in the middle is also greater than what I have on the right.
What I have on the left, remember, I have at least one key.
So if I have any less here or less here, I eat them and so on and so forth.
If let's say I have some key, as I've shown before, I'm gonna eat this one and make it a key.
Then I'm gonna extend here and make it a key and stand here and make this a key.
And so on and so forth.
I make everybody a key.
If let's say I had case.
Case.
And then less than case.
What happens is that again.
Not that this is less.
And this is key.
And I have at least two case.
Everybody's fine.
This is why I need at least two elements, greater or equal than key.
Because at some point I'm going to have two consecutive case which will always eat this less sign.
And that's it.