#include <bits/stdc++.h>
using namespace std;
struct basis {
  int t;
  vector<vector<int> > v;
  basis(int t_) {
    t = t_;
    v.assign(t, vector<int>());
  }
  int msb(int k) {
    for (int i = t - 1; i >= 0; i--)
      if (k >> i & 1) return i;
    return -1;
  }
  void add_vector(int k) {
    if (k == 0) return;
    v[msb(k)].push_back(k);
    for (int i = t - 1; i >= 0; i--) {
      if (v[i].empty()) continue;
      int x = v[i][0];
      for (int j = 1; j < (int)v[i].size(); j++) {
        int y = v[i][j];
        int msk = x ^ y;
        if (msk > 0) v[msb(msk)].push_back(msk);
      }
      while ((int)v[i].size() > 1) v[i].pop_back();
    }
  }
  bool can_generate(int k) {
    for (int i = t - 1; i >= 0; i--) {
      if (k >> i & 1) {
        if (v[i].empty()) return false;
        assert((int)v[i].size() == 1);
        k ^= v[i][0];
      }
    }
    assert(k == 0);
    return true;
  }
};
int main() {
  int n;
  scanf("%d", &n);
  vector<int> v(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    v[i] = v[i - 1] ^ x;
  }
  if (v[n] == 0) {
    printf("-1\n");
    return 0;
  }
  basis B(30);
  B.add_vector(v[n]);
  int ans = 1;
  for (int i = 1; i < n; i++) {
    if (B.can_generate(v[i])) continue;
    B.add_vector(v[i]);
    ans++;
  }
  printf("%d\n", ans);
  return 0;
}

### Prompt

Please formulate a CPP solution to the following problem:

You are given an array a_1, a_2, ..., a_n of integer numbers.

Your task is to divide the array into the maximum number of segments in such a way that:

  * each element is contained in exactly one segment; 
  * each segment contains at least one element; 
  * there doesn't exist a non-empty subset of segments such that bitwise XOR of the numbers from them is equal to 0. 



Print the maximum number of segments the array can be divided into. Print -1 if no suitable division exists.

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the size of the array.

The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^9).

Output

Print the maximum number of segments the array can be divided into while following the given constraints. Print -1 if no suitable division exists.

Examples

Input


4
5 5 7 2


Output


2


Input


3
1 2 3


Output


-1


Input


3
3 1 10


Output


3

Note

In the first example 2 is the maximum number. If you divide the array into \{[5], [5, 7, 2]\}, the XOR value of the subset of only the second segment is 5 ⊕ 7 ⊕ 2 = 0. \{[5, 5], [7, 2]\} has the value of the subset of only the first segment being 5 ⊕ 5 = 0. However, \{[5, 5, 7], [2]\} will lead to subsets \{[5, 5, 7]\} of XOR 7, \{[2]\} of XOR 2 and \{[5, 5, 7], [2]\} of XOR 5 ⊕ 5 ⊕ 7 ⊕ 2 = 5.

Let's take a look at some division on 3 segments — \{[5], [5, 7], [2]\}. It will produce subsets:

  * \{[5]\}, XOR 5; 
  * \{[5, 7]\}, XOR 2; 
  * \{[5], [5, 7]\}, XOR 7; 
  * \{[2]\}, XOR 2; 
  * \{[5], [2]\}, XOR 7; 
  * \{[5, 7], [2]\}, XOR 0; 
  * \{[5], [5, 7], [2]\}, XOR 5; 



As you can see, subset \{[5, 7], [2]\} has its XOR equal to 0, which is unacceptable. You can check that for other divisions of size 3 or 4, non-empty subset with 0 XOR always exists.

The second example has no suitable divisions.

The third example array can be divided into \{[3], [1], [10]\}. No subset of these segments has its XOR equal to 0.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct basis {
  int t;
  vector<vector<int> > v;
  basis(int t_) {
    t = t_;
    v.assign(t, vector<int>());
  }
  int msb(int k) {
    for (int i = t - 1; i >= 0; i--)
      if (k >> i & 1) return i;
    return -1;
  }
  void add_vector(int k) {
    if (k == 0) return;
    v[msb(k)].push_back(k);
    for (int i = t - 1; i >= 0; i--) {
      if (v[i].empty()) continue;
      int x = v[i][0];
      for (int j = 1; j < (int)v[i].size(); j++) {
        int y = v[i][j];
        int msk = x ^ y;
        if (msk > 0) v[msb(msk)].push_back(msk);
      }
      while ((int)v[i].size() > 1) v[i].pop_back();
    }
  }
  bool can_generate(int k) {
    for (int i = t - 1; i >= 0; i--) {
      if (k >> i & 1) {
        if (v[i].empty()) return false;
        assert((int)v[i].size() == 1);
        k ^= v[i][0];
      }
    }
    assert(k == 0);
    return true;
  }
};
int main() {
  int n;
  scanf("%d", &n);
  vector<int> v(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    v[i] = v[i - 1] ^ x;
  }
  if (v[n] == 0) {
    printf("-1\n");
    return 0;
  }
  basis B(30);
  B.add_vector(v[n]);
  int ans = 1;
  for (int i = 1; i < n; i++) {
    if (B.can_generate(v[i])) continue;
    B.add_vector(v[i]);
    ans++;
  }
  printf("%d\n", ans);
  return 0;
}

```