YOU: "You were behind the bar for most of the afternoon?"

SAADAN: "Setting up, mostly. I was running through pours, testing the soda gun, that sort of thing. Made myself a couple of practice drinks, figured nobody would mind."

YOU: "So you were around the venue before doors opened. Anything stand out?"

SAADAN: "Josh came past to film some promotional material, I got to do some cool bar tricks in front of him. Rory was doing his rounds checking on everyone, which, bless him, nobody else organising things does. Oh, and Parsa wandered through at one point. Didn't say much, just sort of looked around and left."

YOU: "Did you see Kevin at all before the event started?"

SAADAN: "Yeah, actually. He walked past the bar heading backstage, maybe, I don't know, twenty minutes before everything happened? Didn't look happy. All tight-jawed. Figured he was just stressed about the night, didn't think much of it."

YOU: "Did anyone else go that way?"

SAADAN: "Someone did, yeah. Didn't get a good look at their face, wasn't really paying attention. But I remember they nudged the soda gun cord out of the way with their foot on the way past. I think their hands were pretty full. Feels weird thinking about it now. A cord was the least of our problems."

Saadan is the bar manager for the ACPC Ball, and he is preparing a row of cocktails for the guests. Each cocktail has an initial flavour score, but Saadan wants to make sure that every guest gets the same five-star experience, so he wants all cocktails to have the same flavour score. To achieve this, Saadan may perform the following mixing technique as many times as he likes:

Select a contiguous group of cocktails. Then, replace the flavour score of the centre cocktail in that group with the median flavour score of the group.

Note that both the centre cocktail and the median are left-biased if the group has an even length. 'Left-biased' means that, if the centre of a group is between two cocktails, the left one is chosen. For instance, the centre of 1 2 3 is 2, and the centre of 1 2 3 4 is also 2 (rather than 3).

Can Saadan make every cocktail have the same flavour score using only this operation?

Input

The first line contains a single integer ~n~ (~1 \leq n \leq 10^5~), the number of cocktails.

The next line contains ~n~ space-separated integers ~a_1,\dots,a_n~ (~1 \leq a_i \leq 10^9~), the flavour scores of the cocktails.

Output

Output Yes or No.

Example

Input 1

7
10 1 2 3 4 5 6

Output 1

No

Input 2

3
5 2 4

Output 2

Yes

Saadan can make every cocktail have flavour score 4. For instance, if he takes the whole row as a group, 4 is the median, so the row becomes 5 4 4. Then, if he takes the first two cocktails as a group, the left-biased median is 4, so the row becomes 4 4 4.

Input 3

5
1 6 5 4 3

Output 3

No

Input 4

5
4 5 1 1 3

Output 4

Yes

Saadan's first operation here must be taking the whole row as a group, creating 4 5 3 1 3. From there, he can easily make every cocktail have flavour score 3.