시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

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