#include <bits/stdc++.h>
int bit[500005], it[500005 * 4], lu[500005 * 4];
int a[500005], vt[500005], last[500005], f[500005], tr[500005];
int n;
void bit_update(int node) {}
int bit_query(int node) { return node; }
void process_lu(int node, int l, int r) {
  if (lu[node] == -1) return;
  if (l < r) {
    int tmp = node << 1;
    if (lu[tmp] < lu[node]) lu[tmp] = lu[node];
    if (lu[tmp + 1] < lu[node]) lu[tmp + 1] = lu[node];
  }
  if (it[node] < lu[node]) it[node] = lu[node];
  lu[node] = -1;
}
void full_it_update(int node, int left, int right, int l, int r, int val) {
  if (r < left || l > right) return;
  process_lu(node, left, right);
  if (l <= left && r >= right) {
    lu[node] = val;
    return;
  }
  int mid = (left + right) >> 1;
  int tmp = node << 1;
  full_it_update(tmp, left, mid, l, r, val);
  full_it_update(tmp + 1, mid + 1, right, l, r, val);
}
void it_update(int l, int r, int val) {
  if (l > r) return;
  full_it_update(1, 1, n, l, r, val);
}
int full_it_query(int node, int left, int right, int l, int r) {
  if (r < left || l > right) return -1;
  process_lu(node, left, right);
  if (l <= left && r >= right) {
    return it[node];
  }
  int mid = (left + right) >> 1;
  int tmp1 = full_it_query(node << 1, left, mid, l, r);
  int tmp2 = full_it_query((node << 1) + 1, mid + 1, right, l, r);
  if (tmp1 > tmp2)
    return tmp1;
  else
    return tmp2;
}
int it_query(int l, int r) { return full_it_query(1, 1, n, l, r); }
void sort(int l, int r) {
  if (l >= r) return;
  int i = l, j = r;
  int chot2 = vt[l + rand() % (r - l + 1)];
  int chot1 = a[chot2];
  while (i <= j) {
    while (a[vt[i]] < chot1 || (a[vt[i]] == chot1 && vt[i] < chot2)) i++;
    while (a[vt[j]] > chot1 || (a[vt[j]] == chot1 && vt[j] > chot2)) j--;
    if (i <= j) {
      if (i < j) {
        int tg = vt[i];
        vt[i] = vt[j];
        vt[j] = tg;
      }
      i++;
      j--;
    }
  }
  sort(i, r);
  sort(l, j);
}
void printresult(int i) {
  if (i <= 0 || f[i] == 0) return;
  if (f[i] == f[i - 1]) {
    printresult(i - 1);
    return;
  }
  printresult(tr[i]);
  printf("%d %d %d %d ", a[tr[i] + 1], a[i], a[tr[i] + 1], a[i]);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    vt[i] = i;
  }
  srand(time(NULL));
  sort(1, n);
  last[vt[1]] = vt[1];
  for (int i = 2; i <= n; i++)
    if (a[vt[i]] == a[vt[i - 1]])
      last[vt[i]] = vt[i - 1];
    else
      last[vt[i]] = vt[i];
  memset(it, 0xFF, 4 * n * sizeof(int));
  memset(lu, 0xFF, 4 * n * sizeof(int));
  memset(bit, 0, n * sizeof(int));
  f[0] = 0;
  for (int i = 1; i <= n; i++) {
    f[i] = f[i - 1];
    int iq1 = -1;
    if (last[i] != i && last[last[i]] != last[i] &&
        last[last[last[i]]] != last[last[i]])
      iq1 = last[last[last[i]]] - 1;
    int iq2 = -1;
    if (last[i] != i) {
      iq2 = it_query(last[i], last[i]);
    }
    if (iq1 < iq2) iq1 = iq2;
    if (iq1 >= 0) {
      int tmp = bit_query(iq1);
      if (tmp >= 0)
        if (f[i] < f[tmp] + 1) {
          f[i] = f[tmp] + 1;
          tr[i] = tmp;
        }
    }
    bit_update(i);
    if (iq2 > 0) it_update(i, i, iq2);
    if (last[i] != i) it_update(last[i] + 1, i - 1, last[i] - 1);
  }
  printf("%d\n", f[n] * 4);
  printresult(n);
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

After you have read all the problems, probably, you think Alex is genius person. That's true! One day he came up with the following task.

Given a sequence of integer numbers a1, a2, ..., an. You are to find a longest sequence b1, b2, ..., b4m, that satisfies the following conditions:

  * b4k + 1 = b4k + 3 for all valid integer k; 
  * b4k + 2 = b4k + 4 for all valid integer k; 
  * sequence b is subsequence of a (not necessarily contiguous subsequence). 



And finally... Alex had given this complicated task to George, and George gave it to you. Help George to cope with the task.

Input

The first line contains a single integer n (1 ≤ n ≤ 5·105). The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

In the first line print a single integer 4m — the maximal possible length of required sequence b. In the second line print 4m integers b1, b2, ..., b4m, that is required sequence.

If there are multiple optimal answers you may print any of them.

Examples

Input

4
3 5 3 5


Output

4
3 5 3 5


Input

10
35 1 2 1 2 35 100 200 100 200


Output

8
1 2 1 2 100 200 100 200

### Response

```cpp
#include <bits/stdc++.h>
int bit[500005], it[500005 * 4], lu[500005 * 4];
int a[500005], vt[500005], last[500005], f[500005], tr[500005];
int n;
void bit_update(int node) {}
int bit_query(int node) { return node; }
void process_lu(int node, int l, int r) {
  if (lu[node] == -1) return;
  if (l < r) {
    int tmp = node << 1;
    if (lu[tmp] < lu[node]) lu[tmp] = lu[node];
    if (lu[tmp + 1] < lu[node]) lu[tmp + 1] = lu[node];
  }
  if (it[node] < lu[node]) it[node] = lu[node];
  lu[node] = -1;
}
void full_it_update(int node, int left, int right, int l, int r, int val) {
  if (r < left || l > right) return;
  process_lu(node, left, right);
  if (l <= left && r >= right) {
    lu[node] = val;
    return;
  }
  int mid = (left + right) >> 1;
  int tmp = node << 1;
  full_it_update(tmp, left, mid, l, r, val);
  full_it_update(tmp + 1, mid + 1, right, l, r, val);
}
void it_update(int l, int r, int val) {
  if (l > r) return;
  full_it_update(1, 1, n, l, r, val);
}
int full_it_query(int node, int left, int right, int l, int r) {
  if (r < left || l > right) return -1;
  process_lu(node, left, right);
  if (l <= left && r >= right) {
    return it[node];
  }
  int mid = (left + right) >> 1;
  int tmp1 = full_it_query(node << 1, left, mid, l, r);
  int tmp2 = full_it_query((node << 1) + 1, mid + 1, right, l, r);
  if (tmp1 > tmp2)
    return tmp1;
  else
    return tmp2;
}
int it_query(int l, int r) { return full_it_query(1, 1, n, l, r); }
void sort(int l, int r) {
  if (l >= r) return;
  int i = l, j = r;
  int chot2 = vt[l + rand() % (r - l + 1)];
  int chot1 = a[chot2];
  while (i <= j) {
    while (a[vt[i]] < chot1 || (a[vt[i]] == chot1 && vt[i] < chot2)) i++;
    while (a[vt[j]] > chot1 || (a[vt[j]] == chot1 && vt[j] > chot2)) j--;
    if (i <= j) {
      if (i < j) {
        int tg = vt[i];
        vt[i] = vt[j];
        vt[j] = tg;
      }
      i++;
      j--;
    }
  }
  sort(i, r);
  sort(l, j);
}
void printresult(int i) {
  if (i <= 0 || f[i] == 0) return;
  if (f[i] == f[i - 1]) {
    printresult(i - 1);
    return;
  }
  printresult(tr[i]);
  printf("%d %d %d %d ", a[tr[i] + 1], a[i], a[tr[i] + 1], a[i]);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    vt[i] = i;
  }
  srand(time(NULL));
  sort(1, n);
  last[vt[1]] = vt[1];
  for (int i = 2; i <= n; i++)
    if (a[vt[i]] == a[vt[i - 1]])
      last[vt[i]] = vt[i - 1];
    else
      last[vt[i]] = vt[i];
  memset(it, 0xFF, 4 * n * sizeof(int));
  memset(lu, 0xFF, 4 * n * sizeof(int));
  memset(bit, 0, n * sizeof(int));
  f[0] = 0;
  for (int i = 1; i <= n; i++) {
    f[i] = f[i - 1];
    int iq1 = -1;
    if (last[i] != i && last[last[i]] != last[i] &&
        last[last[last[i]]] != last[last[i]])
      iq1 = last[last[last[i]]] - 1;
    int iq2 = -1;
    if (last[i] != i) {
      iq2 = it_query(last[i], last[i]);
    }
    if (iq1 < iq2) iq1 = iq2;
    if (iq1 >= 0) {
      int tmp = bit_query(iq1);
      if (tmp >= 0)
        if (f[i] < f[tmp] + 1) {
          f[i] = f[tmp] + 1;
          tr[i] = tmp;
        }
    }
    bit_update(i);
    if (iq2 > 0) it_update(i, i, iq2);
    if (last[i] != i) it_update(last[i] + 1, i - 1, last[i] - 1);
  }
  printf("%d\n", f[n] * 4);
  printresult(n);
  return 0;
}

```