You are given an array of N integers.

In this array in a single operation, you can choose any i (where 1 <= i <= N) such that a[i]>0 and decrease a[i] by 1.

You have to determine is it possible to make the given array sorted (strictly increasing) after using some number of operations (possibly 0) described above.

Input

Input starts with an integer N (1 ≤ N ≤ 100000), number of elements of the array.

Next line contains N separated integers a_i (1 ≤ a_i ≤ 10⁹).

Output

Print "YES" (without quotes), if you can make the array sorted (strictly increasing), otherwise print "NO".

Example

Input:
7
5 2 3 9 88 9 10

Output:
YES