Standing Tall on the Lofty Namsan

Interview

Time limit1sMemory limit512 MB

Summary

Given a sequence, decide whether it strictly increases to some peak position and strictly decreases afterward, printing YES or NO.

Level: Easy3 of 10
Topics: Array, Implementation, Greedy
Solved: No attempts yet

Problem

Standing tall on the lofty Namsan

(omitted)

Raise up upon the bedrock

The ground of Seonrin

A sequence $A$ is a mountain if it increases up to some point and decreases after that point. In other words, there exists a natural number $i$ with $i \leq N$ such that $A_{j-1} < A_j$ for every $j$ with $1 < j \leq i$ , and $A_{j-1} > A_j$ for every $j$ with $i < j \leq N$ .

For example, 1 2 3 4 2 is a mountain because it increases up to the fourth element and decreases after the fourth element ( $i = 4$ ). 1 2 3 4 5 is also a mountain ( $i = 5$ ). However, 1 2 2 3 1 is not a mountain.

Write a program that determines whether a given sequence is a mountain.

Input

The first line gives the length of the sequence, $N$ .

The second line gives $A_1, A_2, \cdots , A_N$ separated by spaces.

Output

If the given sequence $A$ is a mountain, output "YES"; otherwise, output "NO".

Constraints

$1 \leq N \leq 100\,000$

$1 \leq A_i \leq 100\,000$

Examples3

Example 1
Input
```
5
1 2 3 4 2
```
Expected output
```
YES
```
Example 2
Input
```
5
1 2 3 4 5
```
Expected output
```
YES
```
Example 3
Input
```
5
1 2 2 3 1
```
Expected output
```
NO
```