시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 10 8 7 77.778%

## 문제

Daniel likes playing a game with blocks. The game starts with N empty piles of blocks in a line. While playing the game, Daniel does the following operation: he chooses a pile k and puts a block in every pile either to the left or to the right of pile k (including pile k). A valid game state is reached by applying only this operation zero or more times.

For example, in the above image, Daniel played a game with four piles and performed four operations. Firstly, he put one block in each pile to the left of pile 2 (including pile 2), then he put one block in each pile to the right of pile 2 (including pile 2), then he put one block in each pile to the left of pile 3 (including pile 3), and finally, he put one block in each pile to the left of pile 1 (including pile 1).

Given the number of blocks in each pile, determine if it is a valid game state.

## 입력

The first line contains a single integer N (1 ≤ N ≤ 100 000), which is the number of piles.

The second line describes the piles. The line contains N integers, each of which is the number of blocks in a pile. The piles are listed from left to right and each number is at least 0 and at most 100 000.

## 출력

Display if the input describes a valid game state.

## 예제 입력 1

4
3 3 2 1


## 예제 출력 1

YES


## 예제 입력 2

3
1 2 1


## 예제 출력 2

YES


## 예제 입력 3

5
1 2 1 2 1


## 예제 출력 3

NO


## 예제 입력 4

5
1 2 3 2 1


## 예제 출력 4

NO