Peak Patterns

medium

In the remote Himalayas, a sherpa named Raju has developed a unique system to record mountain peaks he encounters during his journeys. As a Google Map contractor mapping unexplored territories, he needs to validate whether certain sequences of peak heights could match his recording system.

Raju's recording system works as follows:

  • He maintains a stack of mountain peak heights (integers).
  • As he climbs upward, he performs two operations: sight (push) and record (pop).
  • A record operation is never done when the stack is empty.
  • Each sight operation assigns the next consecutive integer from Google's height database starting at 0, and adds it to the stack.
  • Raju stops sighting new peaks once he reaches peak number N (a parameter).
  • He stops recording once all peaks have been recorded (i.e., the stack is empty).
  • After each record operation, he writes down the height of the peak.

Given a sequence of integers representing recorded peak heights, determine if it could have been produced by Raju's system for some value of N.

Input Format:

The first line of input contains an integer n n (1n105)(1 \leq n \leq 10^5) denoting the size of the sequence. The second line contains n n integers a1,a2,,an a_1, a_2, \dots, a_n denoting the Google-verified peak height records. (0ai109)(0 \leq a_i \leq 10^9)

Output Format:

Output Yes \mathrm{Yes} if Raju's system could produce the given sequence, and No \mathrm{No} otherwise.

Examples:

Example 1:

Input:

4
0 3 2 1

Output:

Yes

Example 2:

Input:

4
0 3 1 2

Output:

No

Code

Loading Editor...