/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
すぬけくんは，0 と 1 からなる長さ N の整数列を作ろうとしています． 今すぬけ君は空の数列 x を持っており，これから以下の 2 種類の操作を好きな順番で N 回行います．
- 操作A: x の要素をすべて flip する．つまり，0 ならば 1 に変え，1 ならば 0 に変える． その後，x の先頭に 0 を追加する．
- 操作B: x の末尾に 0 を追加する．
0 と 1 からなる長さ N の整数列 A=(A_1,A_2,\cdots,A_N) が与えられます． x を A に一致させることが可能かどうか判定してください．
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 1
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N A_1 A_2 \cdots A_N
出力
x を A に一致させることが可能ならば Yes を，不可能ならば No を出力せよ．
入力例 1
4 0 1 1 0
出力例 1
Yes
以下のように操作すればよいです．
- 始状態：x=()
- 操作Aを行う．x=(0) となる．
- 操作Bを行う．x=(0,0) となる．
- 操作Aを行う．x=(0,1,1) となる．
- 操作Bを行う．x=(0,1,1,0) となる．
入力例 2
4 1 0 0 0
出力例 2
No
入力例 3
4 0 0 0 1
出力例 3
No
Score : 500 points
Problem Statement
Snuke is about to make an integer sequence of length N consisting of 0 and 1. He starts with an empty sequence x and does the following two kinds of operations N times in total, in any order he likes.
- Operation A: Flip every element of x, that is, convert each 0 to 1 and vice versa. Then, add 0 to the beginning of x.
- Operation B: Add 0 to the end of x.
You are given an integer sequence of length N consisting of 0 and 1: A=(A_1,A_2,\cdots,A_N). Determine whether it is possible to make x equal to A.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 1
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
If it is possible to make x equal to A, print Yes; otherwise, print No.
Sample Input 1
4 0 1 1 0
Sample Output 1
Yes
Snuke can do the following.
- Start with x=()
- Do operation A, making x=(0).
- Do operation B, making x=(0,0).
- Do operation A, making x=(0,1,1).
- Do operation B, making x=(0,1,1,0).
Sample Input 2
4 1 0 0 0
Sample Output 2
No
Sample Input 3
4 0 0 0 1
Sample Output 3
No