레몬 게임

시간 제한1초메모리 제한1024 MB

요약
1과 2로 이루어진 수열에서 합이 3인 연속 구간을 반복해 지울 때 모든 원소를 제거할 수 있는지 판별한다.
난이도

보통10점 중 6점

유형
스택, 그리디, 배열
정답자
아직 제출이 없습니다

문제

우현이는 레몬 게임을 즐겨 한다. 이 게임의 규칙은 다음과 같다.

  1. 처음에 NN개의 레몬이 일렬로 놓여 있다. ii번째 레몬에는 A_iA\_i가 적혀 있다. A_iA\_i는 11 또는 22이다.
  2. 연속된 한 개 이상의 레몬 중, 레몬에 적힌 수의 합이 33이 되는 구간을 하나 골라 구간에 포함된 모든 레몬을 모두 제거한다.
  3. 더 이상 제거할 수 있는 레몬이 없을 때까지 22번 과정을 반복한다.

아래 그림은 한 예시 과정을 보여준다.

주어진 모든 레몬을 제거할 수 있는지 판별하라.

입력

입력은 다음과 같은 형식으로 주어진다.

NN

A_1 A_2 ⋯ A_NA\_1 \ A\_2 \ \cdots \ A\_N

출력

첫째 줄에 모든 레몬을 제거할 수 있으면 Yes, 그렇지 않으면 No를 출력한다.

제한

  • 1≤N≤200 0001 \le N \le 200\ 000.
  • 1≤A_i≤21 \le A\_i \le 2 (1≤i≤N1 \le i \le N).

예제2

  1. 예제 1

    입력
    7
    2 1 1 1 2 1 1
    
    예상 출력
    Yes
    
  2. 예제 2

    입력
    3
    2 1 1
    
    예상 출력
    No