Problem: A camera you have accidentally left in a desert has taken an interesting photo. The photo has a resolution of n pixels width, and each column of this photo is all white or all black. Thus, we can represent the photo as a sequence of n zeros and ones, where 0 means that the corresponding column is all white, and 1 means that the corresponding column is black.

You think that this photo can contain a zebra. In this case the whole photo should consist of several (possibly, only one) alternating black and white stripes of equal width. For example, the photo [0, 0, 0, 1, 1, 1, 0, 0, 0] can be a photo of zebra, while the photo [0, 0, 0, 1, 1, 1, 1] can not, because the width of the black stripe is 3, while the width of the white stripe is 4. Can the given photo be a photo of zebra or not?

Input

The first line contains a single integer n (1 ≤ n ≤ 100 000) — the width of the photo.

The second line contains a sequence of integers a1, a2, ..., an (0 ≤ ai ≤ 1) — the description of the photo. If ai is zero, the i-th column is all black. If ai is one, then the i-th column is all white.

Output

If the photo can be a photo of zebra, print "YES" (without quotes). Otherwise, print "NO".

You can print each letter in any case (upper or lower).

Examples

Input

9
0 0 0 1 1 1 0 0 0


Output

YES


Input

7
0 0 0 1 1 1 1


Output

NO


Input

5
1 1 1 1 1


Output

YES


Input

8
1 1 1 0 0 0 1 1


Output

NO


Input

9
1 1 0 1 1 0 1 1 0


Output

NO

Note

The first two examples are described in the statements.

In the third example all pixels are white, so the photo can be a photo of zebra.

In the fourth example the width of the first stripe is equal to three (white color), the width of the second stripe is equal to three (black), and the width of the third stripe is equal to two (white). Thus, not all stripes have equal length, so this photo is not a photo of zebra.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long int MOD = 1e9 + 7;
long long int INF = 1e14;
long long int sub(long long int a, long long int b, long long int p = MOD) {
  return ((a % p) - (b % p) + p) % p;
}
long long int mult(long long int a, long long int b, long long int p = MOD) {
  return ((a % p) * (b % p)) % p;
}
long long int add(long long int a, long long int b, long long int p = MOD) {
  return (a % p + b % p) % p;
}
long long int fpow(long long int n, long long int k, long long int p = MOD) {
  long long int r = 1;
  while (k > 0) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
    k = k >> 1;
  }
  return r;
}
long long int inv(long long int a, long long int p = MOD) {
  return fpow(a, p - 2, p);
}
long long int fdiv(long long int a, long long int b, long long int p = MOD) {
  long long int yinv = inv(b);
  long long int ans = (a * yinv) % p;
  return ans;
}
unsigned long long int I1018 = 1000000000000000000;
const unsigned long long int I10e5 = 100000;
const long long int I10e6 = 1e6;
long long int ZERO = 0;
unsigned long long int I10e9 = 1000000000;
long long int ONE = 1;
void printVecpll(std::vector<pair<long long int, long long int> > v) {
  for (auto p : v) {
    cout << p.first << " " << p.second << endl;
  }
}
template <typename T>
void printVec(std::vector<T> v) {
  for (long long int i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
  }
  cout << endl;
}
std::vector<long long int> read_vec(long long int n) {
  long long int i;
  std::vector<long long int> v(n);
  for (i = 0; i < n; i++) {
    cin >> v[i];
  }
  return v;
}
std::vector<bool> is_prime;
std::vector<long long int> primes;
void sieve(long long int n) {
  is_prime.resize(n + 2, true);
  primes.clear();
  long long int p;
  for (p = 2; p * p <= n; p++) {
    if (is_prime[p]) {
      long long int i;
      for (i = p * p; i <= n; i += p) {
        is_prime[i] = false;
      }
    }
  }
  is_prime[0] = is_prime[1] = false;
  long long int i;
  for (i = 2; i <= n; i++) {
    if (is_prime[i]) {
      primes.emplace_back(i);
    }
  }
}
set<long long int> prime_factor(long long int n) {
  sieve(n);
  long long int i;
  set<long long int> s;
  for (auto p : primes) {
    if (p > sqrt(n)) break;
    while (n % p == 0 && n > 1) {
      s.insert(p);
      n /= p;
    }
  }
  if (n > 1) {
    s.insert(n);
  }
  return s;
}
int main() {
  long long int i;
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long int n;
  cin >> n;
  std::vector<long long int> v = read_vec(n);
  if (n == 1) {
    cout << "YES" << endl;
  } else {
    long long int w = 0;
    set<long long int> s;
    for (i = 0; i < n - 1; i++) {
      if (v[i] == v[i + 1]) {
        w++;
        continue;
      } else {
        w++;
        s.insert(w);
        w = 0;
      }
    }
    w++;
    s.insert(w);
    if (s.size() == 1) {
      cout << "YES" << endl;
    } else {
      cout << "NO" << endl;
    }
  }
  return 0;
}