The lower envelope of a set of s labeled segments on a plane can be obtained by associating each x coordinate with the label of the line segment that intersects the vertical line on x at the lowest point, or with the label 0 if no segment intersects that line. This results in a sequence of intervals of x coordinates where all points inside an interval are associated with the same label, and the corresponding sequence of labels is called the label sequence of that set of segments.

Given a sequence of n labels, figure out if it is the label sequence of some set of n labeled segments.

Input

The first line of the input contains two integers n and s.

The second line of the input contains a sequence of n integers between 0 and s, describing the sequence of supposed labels.

Output

Print "YES" if a solution exists. Otherwise, print "NO".

Constraints

• 1 \le n \le 10^5
• 1 \le s \le 2 \cdot 10^3
• The sequence starts and ends with 0.
• No two consecutive labels of the sequence are the same.

Examples

Input:

8 3
0 1 3 1 3 2 3 0

Output:

YES