Single Modification to Obtain an Oscillating Sequence

Little Qiang loves sequences. One day, he wrote down a sequence. His friend, Amiaba, only likes one kind of sequence: oscillating sequences.

A sequence \(a_1,a_2,\dots,a_n\) is called oscillating if for every integer \(i\) such that \(1 \le i < n\), at least one of the following conditions holds (if the relevant element exists):

• \(a_{2i-1} \le a_{2i}\) and \(a_{2i} \ge a_{2i+1}\)
• \(a_{2i-1} \ge a_{2i}\) and \(a_{2i} \le a_{2i+1}\)

Little Qiang now wonders: is it possible to modify at most one element (or not modify at all) in the given sequence so that it becomes oscillating?

Note: For indices where \(a_{2i+1}\) does not exist, only the adjacent comparison \(a_{2i-1}\) with \(a_{2i}\) is applicable.

inputFormat

The first line contains an integer \(n\) \((1 \le n)\) representing the length of the sequence. The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) representing the sequence.

outputFormat

Output a single line containing Yes if it is possible to obtain an oscillating sequence by modifying at most one element, or No otherwise.

sample

3
1 2 3

Yes