You are given an array $a$ of length $n$ .

In one operation, you can remove at most one element from the array (or not remove any).

Determine if it is possible to make the remaining sequence strictly increasing.

A sequence is called strictly increasing if
$a_1 < a_2 < \ldots < a_k$ .

The first line contains one integer $n$ $(1 \le n \le 2 \cdot 10^5)$ --- the length of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$
.

Print YES if it is possible to remove at most one element so that the sequence becomes strictly increasing.
Otherwise, print NO.

Example 1

Input

5
1 2 3 4 5

Output

YES

Example 2

Input

5
1 2 10 3 4

Output

YES

Example 3

Input

4
1 3 2 1

Output

NO

Almost increasing