블록 떨어뜨리기
시간 제한2초메모리 제한512 MB
각 더미의 블록 수가 주어진다. 어떤 더미에서 왼쪽이나 오른쪽 전부에 블록을 한 번씩 놓는 연산만으로 그 상태가 나올 수 있는지 판정한다.
문제
Daniel은 블록을 가지고 게임을 한다. 게임은 한 줄로 놓인 N개의 빈 더미에서 시작한다. Daniel은 게임을 하면서 다음과 같은 연산을 한다. 더미 k를 하나 고르고, 더미 k의 왼쪽 또는 오른쪽에 있는 모든 더미(더미 k 포함)에 블록을 하나씩 놓는다. 이 연산만 0번 이상 적용해서 도달할 수 있는 상태를 유효한 게임 상태라고 한다.
예를 들어, 위 그림에서 Daniel은 네 개의 더미로 게임을 하면서 네 번의 연산을 수행했다. 먼저 더미 2의 왼쪽에 있는 모든 더미(더미 2 포함)에 블록을 하나씩 놓고, 그다음 더미 2의 오른쪽에 있는 모든 더미(더미 2 포함)에 블록을 하나씩 놓고, 그다음 더미 3의 왼쪽에 있는 모든 더미(더미 3 포함)에 블록을 하나씩 놓고, 마지막으로 더미 1의 왼쪽에 있는 모든 더미(더미 1 포함)에 블록을 하나씩 놓았다.
각 더미에 있는 블록의 수가 주어졌을 때, 주어진 상태가 유효한 게임 상태인지 판별하라.
입력
첫째 줄에는 더미의 수 N (1 ≤ N ≤ 100 000)이 주어진다.
둘째 줄에는 더미를 나타내는 N개의 정수가 주어진다. 각 정수는 한 더미에 있는 블록의 수이며, 더미는 왼쪽에서 오른쪽 순서로 나열되고 각 수는 0 이상 100 000 이하이다.
출력
주어진 입력이 유효한 게임 상태인지 판별하여 출력하라.