#include <bits/stdc++.h>
using namespace std;
template <typename T>
bool chkmin(T &x, T y) {
  return x > y ? x = y, 1 : 0;
}
template <typename T>
bool chkmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
int readint() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
namespace matching {
const int MaxN = 1205;
const int MaxM = MaxN * (MaxN - 1);
int n, m;
int nE, adj[MaxN];
int next[MaxM], go[MaxM];
inline void addEdge(const int &u, const int &v) {
  next[++nE] = adj[u], go[adj[u] = nE] = v;
  next[++nE] = adj[v], go[adj[v] = nE] = u;
}
int n_matches;
int mate[MaxN];
int q_n;
int q[MaxN];
int book_mark;
int book[MaxN];
int type[MaxN];
int fa[MaxN];
int bel[MaxN];
inline void augment(int u) {
  while (u) {
    int nu = mate[fa[u]];
    mate[mate[u] = fa[u]] = u;
    u = nu;
  }
}
inline int get_lca(int u, int v) {
  ++book_mark;
  while (true) {
    if (u) {
      if (book[u] == book_mark) return u;
      book[u] = book_mark;
      u = bel[fa[mate[u]]];
    }
    swap(u, v);
  }
}
inline void go_up(int u, int v, const int &mv) {
  while (bel[u] != mv) {
    fa[u] = v;
    v = mate[u];
    if (type[v] == 1) type[q[++q_n] = v] = 0;
    if (bel[u] == u) bel[u] = mv;
    if (bel[v] == v) bel[v] = mv;
    u = fa[v];
  }
}
inline void after_go_up() {
  for (int u = 1; u <= n; ++u) bel[u] = bel[bel[u]];
}
inline bool match(const int &sv) {
  for (int u = 1; u <= n; ++u) bel[u] = u, type[u] = -1;
  type[q[q_n = 1] = sv] = 0;
  for (int i = 1; i <= q_n; ++i) {
    int u = q[i];
    for (int e = adj[u]; e; e = next[e]) {
      int v = go[e];
      if (!~type[v]) {
        fa[v] = u, type[v] = 1;
        int nu = mate[v];
        if (!nu) {
          augment(v);
          return true;
        }
        type[q[++q_n] = nu] = 0;
      } else if (!type[v] && bel[u] != bel[v]) {
        int lca = get_lca(u, v);
        go_up(u, v, lca);
        go_up(v, u, lca);
        after_go_up();
      }
    }
  }
  return false;
}
inline void calc_max_match() {
  n_matches = 0;
  for (int u = 1; u <= n; ++u)
    if (!mate[u] && match(u)) ++n_matches;
}
}  // namespace matching
int n;
int a[300005], f[605], hv[605], res[300005];
bool vis[300005];
int getf(int x) { return x == f[x] ? x : f[x] = getf(f[x]); }
bool merge(int x, int y) {
  int fx = getf(x), fy = getf(y);
  if (fx == fy) {
    if (hv[fx]) return false;
    hv[fx] = 1;
    return true;
  }
  if (hv[fx] && hv[fy]) return false;
  f[fx] = fy;
  hv[fy] |= hv[fx];
  return true;
}
int main() {
  n = readint();
  for (int i = 1; i <= n; i++) a[i] = readint();
  for (int i = 1; i < n; i++)
    if (a[i] == a[i + 1] && a[i]) vis[a[i]] = 1;
  vis[0] = 1;
  int ans = 0;
  for (int i = 1; i <= 600; i++) ans += vis[i];
  int cnt = 600;
  for (int i = 1; i <= 600; i++) f[i] = i, hv[i] = 0;
  hv[0] = 1;
  for (int i = 1; i <= n; i++) {
    if (a[i] == 0 && (i == 1 || a[i - 1] != 0)) {
      int j = i;
      while (j <= n && !a[j]) j++;
      j--;
      if ((j - i + 1) % 2 == 0) {
        if (vis[a[i - 1]] || vis[a[j + 1]])
          ans += (j - i + 1) / 2;
        else
          matching::addEdge(a[i - 1], a[j + 1]), ans += (j - i + 1) / 2;
      } else {
        ans += (j - i + 1) / 2;
        if (merge(a[i - 1], a[j + 1])) {
          cnt++;
          if (!vis[a[i - 1]]) matching::addEdge(a[i - 1], cnt);
          if (!vis[a[j + 1]]) matching::addEdge(cnt, a[j + 1]);
        }
      }
      i = j;
    }
  }
  matching::n = cnt;
  matching::calc_max_match();
  cnt = 600;
  for (int i = 1; i <= n; i++) res[i] = a[i];
  for (int i = 1; i <= 600; i++) f[i] = i, hv[i] = 0;
  hv[0] = 1;
  for (int i = 1; i <= n; i++) {
    if (a[i] == 0 && (i == 1 || a[i - 1] != 0)) {
      int j = i;
      while (j <= n && !a[j]) j++;
      j--;
      if ((j - i + 1) % 2 == 0) {
        if (vis[a[i - 1]] || vis[a[j + 1]])
          ans += (j - i + 1) / 2;
        else {
          if (matching::mate[a[i - 1]] == a[j + 1]) {
            res[i] = a[i - 1], res[j] = a[j + 1];
            matching::mate[a[i - 1]] = matching::mate[a[j + 1]] = 0;
          }
          ans += (j - i + 1) / 2;
        }
      } else {
        ans += (j - i + 1) / 2;
        if (merge(a[i - 1], a[j + 1])) {
          cnt++;
          if (matching::mate[cnt] == a[i - 1])
            res[i] = a[i - 1];
          else if (matching::mate[cnt] == a[j + 1])
            res[j] = a[j + 1];
        }
      }
      i = j;
    }
  }
  for (int i = 1; i < n; i++)
    if (res[i] == res[i + 1] && res[i]) vis[res[i]] = 1;
  int now = 1;
  while (vis[now]) now++;
  for (int i = 1; i < n; i++) {
    if (!res[i] && !res[i + 1]) {
      res[i] = res[i + 1] = now;
      vis[now] = 1;
      while (vis[now]) now++;
    }
  }
  for (int i = 1; i <= n; i++)
    if (!res[i]) res[i] = 1;
  for (int i = 1; i <= n; i++) printf("%d ", res[i]);
  printf("\n");
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

You are given an array a consisting of n non-negative integers.

You have to replace each 0 in a with an integer from 1 to n (different elements equal to 0 can be replaced by different integers).

The value of the array you obtain is the number of integers k from 1 to n such that the following condition holds: there exist a pair of adjacent elements equal to k (i. e. there exists some i ∈ [1, n - 1] such that a_i = a_{i + 1} = k). If there are multiple such pairs for some integer k, this integer is counted in the value only once.

Your task is to obtain the array with the maximum possible value.

Input

The first line contains one integer n (2 ≤ n ≤ 3 ⋅ 10^5) — the number of elements in the array.

The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ min(n, 600)) — the elements of the array.

Output

Print n integers not less than 1 and not greater than n — the array with the maximum possible value you can obtain.

If there are multiple answers, print any of them.

Examples

Input


4
1 1 0 2


Output


1 1 2 2 


Input


5
0 0 0 0 0


Output


3 1 1 3 3


Input


5
1 2 3 4 5


Output


1 2 3 4 5 


Input


6
1 0 0 0 0 1


Output


1 2 3 3 1 1


Input


3
3 0 2


Output


3 2 2 


Input


5
1 0 2 0 1


Output


1 2 2 1 1 


Input


7
1 0 2 3 1 0 2


Output


1 2 2 3 1 1 2 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
bool chkmin(T &x, T y) {
  return x > y ? x = y, 1 : 0;
}
template <typename T>
bool chkmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
int readint() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
namespace matching {
const int MaxN = 1205;
const int MaxM = MaxN * (MaxN - 1);
int n, m;
int nE, adj[MaxN];
int next[MaxM], go[MaxM];
inline void addEdge(const int &u, const int &v) {
  next[++nE] = adj[u], go[adj[u] = nE] = v;
  next[++nE] = adj[v], go[adj[v] = nE] = u;
}
int n_matches;
int mate[MaxN];
int q_n;
int q[MaxN];
int book_mark;
int book[MaxN];
int type[MaxN];
int fa[MaxN];
int bel[MaxN];
inline void augment(int u) {
  while (u) {
    int nu = mate[fa[u]];
    mate[mate[u] = fa[u]] = u;
    u = nu;
  }
}
inline int get_lca(int u, int v) {
  ++book_mark;
  while (true) {
    if (u) {
      if (book[u] == book_mark) return u;
      book[u] = book_mark;
      u = bel[fa[mate[u]]];
    }
    swap(u, v);
  }
}
inline void go_up(int u, int v, const int &mv) {
  while (bel[u] != mv) {
    fa[u] = v;
    v = mate[u];
    if (type[v] == 1) type[q[++q_n] = v] = 0;
    if (bel[u] == u) bel[u] = mv;
    if (bel[v] == v) bel[v] = mv;
    u = fa[v];
  }
}
inline void after_go_up() {
  for (int u = 1; u <= n; ++u) bel[u] = bel[bel[u]];
}
inline bool match(const int &sv) {
  for (int u = 1; u <= n; ++u) bel[u] = u, type[u] = -1;
  type[q[q_n = 1] = sv] = 0;
  for (int i = 1; i <= q_n; ++i) {
    int u = q[i];
    for (int e = adj[u]; e; e = next[e]) {
      int v = go[e];
      if (!~type[v]) {
        fa[v] = u, type[v] = 1;
        int nu = mate[v];
        if (!nu) {
          augment(v);
          return true;
        }
        type[q[++q_n] = nu] = 0;
      } else if (!type[v] && bel[u] != bel[v]) {
        int lca = get_lca(u, v);
        go_up(u, v, lca);
        go_up(v, u, lca);
        after_go_up();
      }
    }
  }
  return false;
}
inline void calc_max_match() {
  n_matches = 0;
  for (int u = 1; u <= n; ++u)
    if (!mate[u] && match(u)) ++n_matches;
}
}  // namespace matching
int n;
int a[300005], f[605], hv[605], res[300005];
bool vis[300005];
int getf(int x) { return x == f[x] ? x : f[x] = getf(f[x]); }
bool merge(int x, int y) {
  int fx = getf(x), fy = getf(y);
  if (fx == fy) {
    if (hv[fx]) return false;
    hv[fx] = 1;
    return true;
  }
  if (hv[fx] && hv[fy]) return false;
  f[fx] = fy;
  hv[fy] |= hv[fx];
  return true;
}
int main() {
  n = readint();
  for (int i = 1; i <= n; i++) a[i] = readint();
  for (int i = 1; i < n; i++)
    if (a[i] == a[i + 1] && a[i]) vis[a[i]] = 1;
  vis[0] = 1;
  int ans = 0;
  for (int i = 1; i <= 600; i++) ans += vis[i];
  int cnt = 600;
  for (int i = 1; i <= 600; i++) f[i] = i, hv[i] = 0;
  hv[0] = 1;
  for (int i = 1; i <= n; i++) {
    if (a[i] == 0 && (i == 1 || a[i - 1] != 0)) {
      int j = i;
      while (j <= n && !a[j]) j++;
      j--;
      if ((j - i + 1) % 2 == 0) {
        if (vis[a[i - 1]] || vis[a[j + 1]])
          ans += (j - i + 1) / 2;
        else
          matching::addEdge(a[i - 1], a[j + 1]), ans += (j - i + 1) / 2;
      } else {
        ans += (j - i + 1) / 2;
        if (merge(a[i - 1], a[j + 1])) {
          cnt++;
          if (!vis[a[i - 1]]) matching::addEdge(a[i - 1], cnt);
          if (!vis[a[j + 1]]) matching::addEdge(cnt, a[j + 1]);
        }
      }
      i = j;
    }
  }
  matching::n = cnt;
  matching::calc_max_match();
  cnt = 600;
  for (int i = 1; i <= n; i++) res[i] = a[i];
  for (int i = 1; i <= 600; i++) f[i] = i, hv[i] = 0;
  hv[0] = 1;
  for (int i = 1; i <= n; i++) {
    if (a[i] == 0 && (i == 1 || a[i - 1] != 0)) {
      int j = i;
      while (j <= n && !a[j]) j++;
      j--;
      if ((j - i + 1) % 2 == 0) {
        if (vis[a[i - 1]] || vis[a[j + 1]])
          ans += (j - i + 1) / 2;
        else {
          if (matching::mate[a[i - 1]] == a[j + 1]) {
            res[i] = a[i - 1], res[j] = a[j + 1];
            matching::mate[a[i - 1]] = matching::mate[a[j + 1]] = 0;
          }
          ans += (j - i + 1) / 2;
        }
      } else {
        ans += (j - i + 1) / 2;
        if (merge(a[i - 1], a[j + 1])) {
          cnt++;
          if (matching::mate[cnt] == a[i - 1])
            res[i] = a[i - 1];
          else if (matching::mate[cnt] == a[j + 1])
            res[j] = a[j + 1];
        }
      }
      i = j;
    }
  }
  for (int i = 1; i < n; i++)
    if (res[i] == res[i + 1] && res[i]) vis[res[i]] = 1;
  int now = 1;
  while (vis[now]) now++;
  for (int i = 1; i < n; i++) {
    if (!res[i] && !res[i + 1]) {
      res[i] = res[i + 1] = now;
      vis[now] = 1;
      while (vis[now]) now++;
    }
  }
  for (int i = 1; i <= n; i++)
    if (!res[i]) res[i] = 1;
  for (int i = 1; i <= n; i++) printf("%d ", res[i]);
  printf("\n");
  return 0;
}

```