#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long int num) {
  bool flag = true;
  for (long long int i = 2; i <= num / 2; i++) {
    if (num % i == 0) {
      flag = false;
      break;
    }
  }
  return flag;
}
bool isPowerOfTwo(int n) {
  if (n == 0) return false;
  return (ceil(log2(n)) == floor(log2(n)));
}
long long int OcD(long long int n) {
  long long int x = 0;
  long long int base = 1;
  long long int t = n;
  while (t != 0) {
    long long int xp = t % 10;
    t = t / 10;
    x += xp * base;
    base = base * 8;
  }
  return x;
}
long long int DcO(long long int n) {
  int remainder;
  long octal = 0, i = 1;
  while (n != 0) {
    remainder = n % 8;
    n = n / 8;
    octal = octal + (remainder * i);
    i = i * 10;
  }
  return octal;
}
long long int DropLeadingDigit(long long int number) {
  return (number %
          (long long int)pow((long double)10,
                             (long double)floor(log((long double)number) /
                                                log((long double)10))));
}
long long int remove_leftmost_digit(long long int n) {
  static char temp[11];
  sprintf(temp, "%d", n);
  return atoi(temp + 1);
}
void Remove(char str[], long long int n) {
  set<char> s(str, str + n - 1);
  for (set<char>::iterator it = s.begin(); it != s.end(); it++) {
    cout << *it;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long int a, b, c, d = 0, e = 0, f, i, k, j, l, x[1000], y[1000];
  string s, p, t;
  cin >> a;
  for (i = 1; i <= a; i++) {
    cin >> x[i];
    if (x[i] % 2 == 0) {
      f = i;
      e++;
    } else {
      k = i;
      d++;
    }
  }
  if (e > d)
    cout << k << endl;
  else
    cout << f << endl;
  return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

Bob is preparing to pass IQ test. The most frequent task in this test is to find out which one of the given n numbers differs from the others. Bob observed that one number usually differs from the others in evenness. Help Bob — to check his answers, he needs a program that among the given n numbers finds one that is different in evenness.

Input

The first line contains integer n (3 ≤ n ≤ 100) — amount of numbers in the task. The second line contains n space-separated natural numbers, not exceeding 100. It is guaranteed, that exactly one of these numbers differs from the others in evenness.

Output

Output index of number that differs from the others in evenness. Numbers are numbered from 1 in the input order.

Examples

Input

5
2 4 7 8 10


Output

3


Input

4
1 2 1 1


Output

2

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long int num) {
  bool flag = true;
  for (long long int i = 2; i <= num / 2; i++) {
    if (num % i == 0) {
      flag = false;
      break;
    }
  }
  return flag;
}
bool isPowerOfTwo(int n) {
  if (n == 0) return false;
  return (ceil(log2(n)) == floor(log2(n)));
}
long long int OcD(long long int n) {
  long long int x = 0;
  long long int base = 1;
  long long int t = n;
  while (t != 0) {
    long long int xp = t % 10;
    t = t / 10;
    x += xp * base;
    base = base * 8;
  }
  return x;
}
long long int DcO(long long int n) {
  int remainder;
  long octal = 0, i = 1;
  while (n != 0) {
    remainder = n % 8;
    n = n / 8;
    octal = octal + (remainder * i);
    i = i * 10;
  }
  return octal;
}
long long int DropLeadingDigit(long long int number) {
  return (number %
          (long long int)pow((long double)10,
                             (long double)floor(log((long double)number) /
                                                log((long double)10))));
}
long long int remove_leftmost_digit(long long int n) {
  static char temp[11];
  sprintf(temp, "%d", n);
  return atoi(temp + 1);
}
void Remove(char str[], long long int n) {
  set<char> s(str, str + n - 1);
  for (set<char>::iterator it = s.begin(); it != s.end(); it++) {
    cout << *it;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long int a, b, c, d = 0, e = 0, f, i, k, j, l, x[1000], y[1000];
  string s, p, t;
  cin >> a;
  for (i = 1; i <= a; i++) {
    cin >> x[i];
    if (x[i] % 2 == 0) {
      f = i;
      e++;
    } else {
      k = i;
      d++;
    }
  }
  if (e > d)
    cout << k << endl;
  else
    cout << f << endl;
  return 0;
}

```