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 
20
1 0 4 3 0 0 0 2 1 0 0 4 2 0 0 4 2 0 0 3
 5
0 0 0 0 0
 14
0 14 4 1 0 4 9 0 0 0 8 4 0 1
 6
1 0 0 0 0 1
 100
0 0 77 89 33 93 0 0 0 40 0 2 93 56 0 60 94 0 2 43 0 82 43 74 4 59 80 9 73 7 33 90 5 12 0 96 0 37 0 72 62 0 59 0 0 0 0 71 26 22 24 0 0 0 0 34 86 87 13 0 0 1 77 0 99 0 0 65 97 6 14 0 0 0 0 59 73 0 0 18 0 3 76 39 52 0 0 56 0 0 58 0 84 0 95 0 0 0 58 0
 12
11 10 0 12 5 2 0 6 0 2 6 2
 16
0 0 0 15 16 0 0 4 2 0 13 0 0 13 0 2
 9
5 1 0 2 0 1 4 0 7

1 1 4 3 3 5 5 2 1 6 6 4 2 2 4 4 2 7 7 3 
 1 1 2 2 1 
 14 14 4 1 1 4 9 9 2 2 8 4 4 1
 1 1 1 2 2 1 
 4 4 77 89 33 93 93 5 5 40 40 2 93 56 60 60 94 2 2 43 43 82 43 74 4 59 80 9 73 7 33 90 5 12 12 96 37 37 72 72 62 62 59 6 6 7 7 71 26 22 24 24 8 8 34 34 86 87 13 13 1 1 77 77 99 99 65 65 97 6 14 14 9 9 59 59 73 73 18 18 3 3 76 39 52 52 56 56 10 10 58 84 84 1 95 95 11 11 58 58 
 11 10 10 12 5 2 2 6 6 2 6 2 
 1 1 15 15 16 16 4 4 2 2 13 3 3 13 13 2 
 5 1 1 2 2 1 4 4 7 

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

// Actual solution is at the bottom

#undef NDEBUG

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>
// AtCoder library from https://github.com/atcoder/ac-library
// #include "../atcoder/all"

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()

using namespace std;

typedef int64_t int64;
typedef pair<int, int> ii;

struct Edge {
  int dest;
  int start;
  int finish;

  Edge(int dest, int start, int finish) : dest(dest), start(start), finish(finish) {}
};

// code by Min_25
// from https://gist.github.com/min-25/aed29a23b004505d2094a5cddaf56ff9
class MaximumMatching {
  /*
    Maximum Cardinality Matching in General Graphs.
    - O(\sqrt{n} m \log_{\max\{2, 1 + m/n\}} n) time
    - O(n + m) space
    Note: each vertex is 1-indexed.
    Ref:
      Harold N. Gabow,
      "The Weighted Matching Approach to Maximum Cardinality Matching" (2017)
      (https://arxiv.org/abs/1703.03998)
  */
 public:
  struct Edge { int from, to; };
  static constexpr int Inf = 1 << 30;

 private:
  enum Label {
    kInner = -1, // should be < 0
    kFree = 0    // should be 0
  };
  struct Link { int from, to; };
  struct Log { int v, par; };

  struct LinkedList {
    LinkedList() {}
    LinkedList(int N, int M) : N(N), next(M) { clear(); }
    void clear() { head.assign(N, -1); }
    void push(int h, int u) { next[u] = head[h], head[h] = u; }
    int N;
    vector<int> head, next;
  };

  template <typename T>
  struct Queue {
    Queue() {}
    Queue(int N) : qh(0), qt(0), data(N) {}
    T operator [] (int i) const { return data[i]; }
    void enqueue(int u) { data[qt++] = u; }
    int dequeue() { return data[qh++]; }
    bool empty() const { return qh == qt; }
    void clear() { qh = qt = 0; }
    int size() const { return qt; }
    int qh, qt;
    vector<T> data;
  };

  struct DisjointSetUnion {
    DisjointSetUnion() {}
    DisjointSetUnion(int N) : par(N) {
      for (int i = 0; i < N; ++i) par[i] = i;
    }
    int find(int u) { return par[u] == u ? u : (par[u] = find(par[u])); }
    void unite(int u, int v) {
      u = find(u), v = find(v);
      if (u != v) par[v] = u;
    }
    vector<int> par;
  };

 public:
  MaximumMatching(int N, const vector<Edge>& in)
      : N(N), NH(N >> 1), ofs(N + 2, 0), edges(in.size() * 2) {

    for (auto& e : in) ofs[e.from + 1] += 1, ofs[e.to + 1] += 1;
    for (int i = 1; i <= N + 1; ++i) ofs[i] += ofs[i - 1];
    for (auto& e : in) {
      edges[ofs[e.from]++] = e; edges[ofs[e.to]++] = {e.to, e.from};
    }
    for (int i = N + 1; i > 0; --i) ofs[i] = ofs[i - 1];
    ofs[0] = 0;
  }

  int maximum_matching() {
    initialize();
    int match = 0;
    while (match * 2 + 1 < N) {
      reset_count();
      bool has_augmenting_path = do_edmonds_search();
      if (!has_augmenting_path) break;
      match += find_maximal();
      clear();
    }
    return match;
  }

  vector<int> get_mate(){
    return mate;
  }

 private:
  void reset_count() {
    time_current_ = 0; time_augment_ = Inf;
    contract_count_ = 0; outer_id_ = 1;
    dsu_changelog_size_ = dsu_changelog_last_ = 0;
  }

  void clear() {
    que.clear();
    for (int u = 1; u <= N; ++u) potential[u] = 1;
    for (int u = 1; u <= N; ++u) dsu.par[u] = u;
    for (int t = time_current_; t <= N / 2; ++t) list.head[t] = -1;
    for (int u = 1; u <= N; ++u) blossom.head[u] = -1;
  }

  // first phase

  inline void grow(int x, int y, int z) {
    label[y] = kInner;
    potential[y] = time_current_; // visited time
    link[z] = {x, y}; label[z] = label[x];
    potential[z] = time_current_ + 1;
    que.enqueue(z);
  }

  void contract(int x, int y) {
    int bx = dsu.find(x), by = dsu.find(y);
    const int h = -(++contract_count_) + kInner;
    label[mate[bx]] = label[mate[by]] = h;
    int lca = -1;
    while (1) {
      if (mate[by] != 0) swap(bx, by);
      bx = lca = dsu.find(link[bx].from);
      if (label[mate[bx]] == h) break;
      label[mate[bx]] = h;
    }
    for (auto bv : {dsu.par[x], dsu.par[y]}) {
      for (; bv != lca; bv = dsu.par[link[bv].from]) {
        int mv = mate[bv];
        link[mv] = {x, y}; label[mv] = label[x];
        potential[mv] = 1 + (time_current_ - potential[mv]) + time_current_;
        que.enqueue(mv);
        dsu.par[bv] = dsu.par[mv] = lca;
        dsu_changelog[dsu_changelog_last_++] = {bv, lca};
        dsu_changelog[dsu_changelog_last_++] = {mv, lca};
      }
    }
  }

  bool find_augmenting_path() {
    while (!que.empty()) {
      int x = que.dequeue(), lx = label[x], px = potential[x], bx = dsu.find(x);
      for (int eid = ofs[x]; eid < ofs[x + 1]; ++eid) {
        int y = edges[eid].to;
        if (label[y] > 0) { // outer blossom/vertex
          int time_next = (px + potential[y]) >> 1;
          if (lx != label[y]) {
            if (time_next == time_current_) return true;
            time_augment_ = min(time_next, time_augment_);
          } else {
            if (bx == dsu.find(y)) continue;
            if (time_next == time_current_) {
              contract(x, y); bx = dsu.find(x);
            } else if (time_next <= NH) list.push(time_next, eid);
          }
        } else if (label[y] == kFree) { // free vertex
          int time_next = px + 1;
          if (time_next == time_current_) grow(x, y, mate[y]);
          else if (time_next <= NH) list.push(time_next, eid);
        }
      }
    }
    return false;
  }

  bool adjust_dual_variables() {
    // Return true if the current matching is maximum.
    const int time_lim = min(NH + 1, time_augment_);
    for (++time_current_; time_current_ <= time_lim; ++time_current_) {
      dsu_changelog_size_ = dsu_changelog_last_;
      if (time_current_ == time_lim) break;
      bool updated = false;
      for (int h = list.head[time_current_]; h >= 0; h = list.next[h]) {
        auto& e = edges[h]; int x = e.from, y = e.to;
        if (label[y] > 0) {
          // Case: outer -- (free => inner => outer)
          if (potential[x] + potential[y] != (time_current_ << 1)) continue;
          if (dsu.find(x) == dsu.find(y)) continue;
          if (label[x] != label[y]) { time_augment_ = time_current_; return false; }
          contract(x, y); updated = true;
        } else if (label[y] == kFree) {
          grow(x, y, mate[y]); updated = true;
        }
      }
      list.head[time_current_] = -1;
      if (updated) return false;
    }
    return time_current_ > NH;
  }

  bool do_edmonds_search() {
    label[0] = kFree;
    for (int u = 1; u <= N; ++u) {
      if (mate[u] == 0) {
        que.enqueue(u); label[u] = u; // component id
      } else label[u] = kFree;
    }
    while (1) {
      if (find_augmenting_path()) break;
      bool maximum = adjust_dual_variables();
      if (maximum) return false;
      if (time_current_ == time_augment_) break;
    }
    for (int u = 1; u <= N; ++u) {
      if (label[u] > 0) potential[u] -= time_current_;
      else if (label[u] < 0) potential[u] = 1 + (time_current_ - potential[u]);
    }
    return true;
  }

  // second phase

  void rematch(int v, int w) {
    int t = mate[v]; mate[v] = w;
    if (mate[t] != v) return;
    if (link[v].to == dsu.find(link[v].to)) {
      mate[t] = link[v].from;
      rematch(mate[t], t);
    } else {
      int x = link[v].from, y = link[v].to;
      rematch(x, y); rematch(y, x);
    }
  }

  bool dfs_augment(int x, int bx) {
    int px = potential[x], lx = label[bx];
    for (int eid = ofs[x]; eid < ofs[x + 1]; ++eid) {
      int y = edges[eid].to;
      if (px + potential[y] != 0) continue;
      int by = dsu.find(y), ly = label[by];
      if (ly > 0) { // outer
        if (lx >= ly) continue;
        int stack_beg = stack_last_;
        for (int bv = by; bv != bx; bv = dsu.find(link[bv].from)) {
          int bw = dsu.find(mate[bv]);
          stack[stack_last_++] = bw; link[bw] = {x, y};
          dsu.par[bv] = dsu.par[bw] = bx;
        }
        while (stack_last_ > stack_beg) {
          int bv = stack[--stack_last_];
          for (int v = blossom.head[bv]; v >= 0; v = blossom.next[v]) {
            if (!dfs_augment(v, bx)) continue;
            stack_last_ = stack_beg;
            return true;
          }
        }
      } else if (ly == kFree) {
        label[by] = kInner; int z = mate[by];
        if (z == 0) { rematch(x, y); rematch(y, x); return true; }
        int bz = dsu.find(z);
        link[bz] = {x, y}; label[bz] = outer_id_++;
        for (int v = blossom.head[bz]; v >= 0; v = blossom.next[v]) {
          if (dfs_augment(v, bz)) return true;
        }
      }
    }
    return false;
  }

  int find_maximal() {
    // discard blossoms whose potential is 0.
    for (int u = 1; u <= N; ++u) dsu.par[u] = u;
    for (int i = 0; i < dsu_changelog_size_; ++i) {
      dsu.par[dsu_changelog[i].v] = dsu_changelog[i].par;
    }
    for (int u = 1; u <= N; ++u) {
      label[u] = kFree; blossom.push(dsu.find(u), u);
    }
    int ret = 0;
    for (int u = 1; u <= N; ++u) if (!mate[u]) {
        int bu = dsu.par[u];
        if (label[bu] != kFree) continue;
        label[bu] = outer_id_++;
        for (int v = blossom.head[bu]; v >= 0; v = blossom.next[v]) {
          if (!dfs_augment(v, bu)) continue;
          ret += 1;
          break;
        }
      }
    assert(ret >= 1);
    return ret;
  }

  // init

  void initialize() {
    que = Queue<int>(N);

    mate.assign(N + 1, 0);
    potential.assign(N + 1, 1);
    label.assign(N + 1, kFree);
    link.assign(N + 1, {0, 0});

    dsu_changelog.resize(N);

    dsu = DisjointSetUnion(N + 1);
    list = LinkedList(NH + 1, edges.size());

    blossom = LinkedList(N + 1, N + 1);
    stack.resize(N); stack_last_ = 0;
  }

 private:
  const int N, NH;
  vector<int> ofs; vector<Edge> edges;

  Queue<int> que;

  vector<int> mate, potential;
  vector<int> label; vector<Link> link;

  vector<Log> dsu_changelog; int dsu_changelog_last_, dsu_changelog_size_;

  DisjointSetUnion dsu;
  LinkedList list, blossom;
  vector<int> stack; int stack_last_;

  int time_current_, time_augment_;
  int contract_count_, outer_id_;
};

class GMaksimizatsiyaParSosedei {
 public:
  void solveOne() {
    int n;
    cin >> n;
    vector<int> count(n + 1);
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
      ++count[a[i]];
    }

    int free = 1;

    auto handleEvenBoring = [&](int start, int finish) {
      assert(a[start] == 0);
      assert(a[finish] == 0);
      for (int j = start; j + 1 <= finish; j += 2) {
        while (count[free] > 0) ++free;
        a[j] = a[j + 1] = free;
        count[free] += 2;
      }
    };

    auto handleEvenInteresting = [&](int start, int finish) {
      assert(a[start] == 0);
      assert(a[finish] == 0);
      for (int j = start + 1; j + 1 <= finish; j += 2) {
        while (count[free] > 0) ++free;
        a[j] = a[j + 1] = free;
        count[free] += 2;
      }
      a[start] = a[start - 1];
      ++count[a[start]];
      a[finish] = a[finish + 1];
      ++count[a[finish]];
    };

    vector<vector<Edge>> oddEdges(n + 1);
    vector<vector<Edge>> evenEdges(n + 1);
    int start = 0;
    for (int i = 0; i <= n; ++i) {
      if (i == n || a[i] != 0) {
        int finish = i - 1;
        if (start <= finish) {
          if (start == 0) {
            for (int j = start; j + 1 <= finish; j += 2) {
              while (count[free] > 0) ++free;
              a[j] = a[j + 1] = free;
              count[free] += 2;
            }
            if (a[finish] == 0) {
              if (finish + 1 < n) {
                a[finish] = a[finish + 1];
              } else {
                while (count[free] > 0) ++free;
                a[finish] = free;
              }
              ++count[a[finish]];
            }
          } else if (finish == n - 1) {
            for (int j = finish; j - 1 >= start; j -= 2) {
              while (count[free] > 0) ++free;
              a[j] = a[j - 1] = free;
              count[free] += 2;
            }
            if (a[start] == 0) {
              if (start > 0) {
                a[start] = a[start - 1];
              } else {
                while (count[free] > 0) ++free;
                a[start] = free;
              }
              ++count[a[start]];
            }
          } else {
            if ((finish - start + 1) % 2 == 0) {
              // even block
              evenEdges[min(a[start - 1], a[finish + 1])].emplace_back(max(a[start - 1], a[finish + 1]), start, finish);
            } else {
              // odd block
              oddEdges[a[start - 1]].emplace_back(a[finish + 1], start, finish);
              oddEdges[a[finish + 1]].emplace_back(a[start - 1], start, finish);
            }
          }
        }
        start = i + 1;
      }
    }

    auto handleOdd = [&](int start, int finish, int to) {
      assert(a[start] == 0);
      assert(a[finish] == 0);
      if (to == a[start - 1]) {
        for (int j = finish; j - 1 >= start; j -= 2) {
          while (count[free] > 0) ++free;
          a[j] = a[j - 1] = free;
          count[free] += 2;
        }
        a[start] = a[start - 1];
        ++count[a[start]];
      } else if (to == a[finish + 1]) {
        for (int j = start; j + 1 <= finish; j += 2) {
          while (count[free] > 0) ++free;
          a[j] = a[j + 1] = free;
          count[free] += 2;
        }
        a[finish] = a[finish + 1];
        ++count[a[finish]];
      } else {
        assert(false);
      }
    };

    vector<bool> satisfied(n + 1);
    for (int i = 0; i + 1 < n; ++i) if (a[i] > 0 && a[i] == a[i + 1]) satisfied[a[i]] = true;
    n = min(n, 600);
    vector<int> oddComponent(n + 1, -1);

    int satisfiedIndex = -1;
    vector<int> component;
    auto oddDfs = [&](auto self, int at, int viaStart) {
      if (at < 0) return;
      if (satisfied[at]) {
        satisfiedIndex = at;
      }
      oddComponent[at] = -2;
      component.push_back(at);
      for (auto e : oddEdges[at]) {
        if (e.start == viaStart || a[e.start] != 0) continue;
        if (oddComponent[e.dest] == -1) {
          self(self, e.dest, e.start);
        } else {
          handleOdd(e.start, e.finish, at);
          satisfied[at] = true;
          satisfiedIndex = at;
        }
      }
    };

    auto oddDfs2 = [&](auto self, auto at) {
      if (at < 0) return;
      for (auto e : oddEdges[at]) {
        if (a[e.start] == 0) {
          handleOdd(e.start, e.finish, e.dest);
          satisfied[e.dest] = true;
          self(self, e.dest);
        }
      }
    };

    int oddComps = 0;
    for (int i = 1; i <= n; ++i) if (oddComponent[i] == -1) {
      satisfiedIndex = -1;
      component.clear();
      oddDfs(oddDfs, i, -1);
      if (satisfiedIndex >= 0) {
        oddDfs2(oddDfs2, satisfiedIndex);
        for (int x : component) {
          assert(satisfied[x]);
        }
      } else {
        for (int x : component) oddComponent[x] = oddComps;
        ++oddComps;
      }
    }

    vector<MaximumMatching::Edge> medges;
    for (int i = 1; i <= n; ++i) {
      for (Edge e : evenEdges[i]) {
        MaximumMatching::Edge ee;
        ee.from = oddComponent[i - 1] + 1;
        ee.to = oddComponent[e.dest - 1] + 1;
        if (ee.from > 0 && ee.to > 0 && ee.from != ee.to)
          medges.push_back(ee);
      }
    }
    MaximumMatching matching(oddComps, medges);
    matching.maximum_matching();

    auto mate = matching.get_mate();

    for (int i = 1; i <= n; ++i) if (oddComponent[i] >= 0 && mate[oddComponent[i] + 1] > 0) {
      int us = oddComponent[i];
      int other = mate[oddComponent[i] + 1] - 1;
      for (Edge e : evenEdges[i]) {
        if (oddComponent[e.dest] == other) {
          handleEvenInteresting(e.start, e.finish);
          oddDfs2(oddDfs2, e.start);
          oddDfs2(oddDfs2, e.finish);
          mate[us + 1] = mate[other + 1] = 0;
          break;
        }
      }
    }

    for (int i = 0; i < oddComps; ++i) assert(mate[i + 1] == 0);

    for (int i = 1; i <= n; ++i) {
      for (Edge e : evenEdges[i]) {
        if (a[e.start] == 0) {
          handleEvenBoring(e.start, e.finish);
        }
      }
    }

    for (int i = 1; i <= n; ++i) {
      oddDfs2(oddDfs2, i);
    }

    for (int x : a) {
      assert(x > 0);
      cout << x << " ";
    }
    cout << "\n";
  }

  void solve() {
    int nt = 1;
    for (int it = 0; it < nt; ++it) {
      // cout << "Case #" << (it + 1) << ": ";
      solveOne();
    }
  }
};

// #define st_mtimespec st_mtim

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    GMaksimizatsiyaParSosedei solver;


    solver.solve();
    return 0;
}
