#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / abs1(a) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitnum(long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
inline int bitmaxl(long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
  if (mod == -1) mod = 1000000007;
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
const int maxn = 300100;
int arr[maxn];
int addnum[maxn];
int n, nad;
struct tree_array {
  pair<int, int> num[1 << 18];
  int n, bigwei;
  void init(int nn = 1 << 18) {
    n = nn;
    while (lowb(nn) != nn) nn -= lowb(nn);
    bigwei = nn;
    n = bigwei * 2;
    for (int i = 0; i < n; i++) {
      num[i] = make_pair(0, -1);
    }
  }
  void upd(int no, pair<int, int> add) {
    while (no <= n) {
      num[no] = max(add, num[no]);
      no += lowb(no);
    }
  }
  pair<int, int> que(int no) {
    pair<int, int> ans = make_pair(0, -1);
    while (no) {
      ans = max(ans, num[no]);
      no -= lowb(no);
    }
    return ans;
  }
};
tree_array ta;
int lastcan[maxn * 2], lastcan1[maxn];
int val[maxn], val1[maxn];
pair<int, int> rval[maxn];
int trans[maxn], ltrans;
int used[maxn];
int get(int no) {
  if (no < n) return val[no];
  return val1[no - n];
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d", &n);
  ltrans = 0;
  for (int i = 0; i < n; i++) {
    scanf("%d", arr + i);
    trans[ltrans++] = arr[i];
  }
  scanf("%d", &nad);
  for (int i = 0; i < nad; i++) {
    scanf("%d", addnum + i);
    trans[ltrans++] = addnum[i];
  }
  sort(addnum, addnum + nad);
  sort(trans, trans + ltrans);
  ltrans = unique(trans, trans + ltrans) - trans;
  for (int i = 0; i < n; i++)
    if (arr[i] != -1) arr[i] = find(arr[i], trans, ltrans) + 3;
  for (int i = 0; i < nad; i++) addnum[i] = find(addnum[i], trans, ltrans) + 3;
  memset(lastcan1, -1, sizeof(lastcan1));
  ta.init(ltrans + 10);
  for (int i = 0; i < n; i++) {
    if (arr[i] == -1) {
      for (int link = -1, j = 0; j < nad; j++) {
        while (addnum[link + 1] < addnum[j]) link++;
        if (link == -1)
          rval[j] = make_pair(1, -1);
        else
          rval[j] = make_pair(val1[link] + 1, lastcan1[link]);
      }
      pair<int, int> temp = make_pair(0, -1);
      int rlink = 0;
      for (int j = 0; j < nad; j++) {
        while (rlink < addnum[j] - 1) {
          rlink++;
          temp = max(temp, ta.num[rlink]);
        }
        if (temp.first + 1 > val1[j]) {
          val1[j] = temp.first + 1;
          lastcan1[j] = temp.second;
        }
        if (rval[j].first > val1[j]) {
          val1[j] = rval[j].first;
          lastcan1[j] = rval[j].second;
        }
      }
    } else {
      pair<int, int> temp = ta.que(arr[i] - 1);
      temp.first++;
      int loc = find(arr[i] - 1, addnum, nad, 1, 0);
      if (loc != -1) {
        if (temp.first < val1[loc] + 1) {
          temp.first = val1[loc] + 1;
          temp.second = lastcan1[loc];
        }
      }
      val[i] = temp.first;
      lastcan[i] = temp.second;
      temp.second = i;
      ta.upd(arr[i], temp);
    }
  }
  int be = 0;
  for (int i = 0; i < n; i++)
    if (val[i] > val[be]) be = i;
  for (int i = 0; i < nad; i++)
    if (val1[i] > get(be)) be = i + n;
  for (int i = 0; i < n; i++)
    if (arr[i] >= 3) {
      assert(trans[arr[i] - 3] != -1);
    }
  int link = nad - 1;
  int last = 1000000007;
  if (be < n) last = arr[be];
  for (int i = 0; i < nad; i++) {
    lastcan[i + n] = lastcan1[i];
    val[i + n] = val1[i];
  }
  for (; be >= 0; be = lastcan[be]) {
    int nxt;
    if (lastcan[be] == -1)
      nxt = 0;
    else
      nxt = arr[lastcan[be]];
    while (link >= 0 && addnum[link] >= last) link--;
    for (int j = be; j > lastcan[be]; j--)
      if (arr[j] == -1) {
        while (link >= 0 && addnum[link] >= last) link--;
        if (link >= 0 && addnum[link] > nxt) {
          arr[j] = addnum[link];
          used[link] = 1;
          last = addnum[link];
          link--;
        }
      }
    last = nxt;
  }
  link = 0;
  for (int i = 0; i < n; i++)
    if (arr[i] == -1) {
      while (used[link]) link++;
      arr[i] = addnum[link];
      used[link] = 1;
    }
  for (int i = 0; i < n; i++) {
    cout << trans[arr[i] - 3] << ' ';
  }
  cout << endl;
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

Note that the memory limit in this problem is less than usual.

Let's consider an array consisting of positive integers, some positions of which contain gaps.

We have a collection of numbers that can be used to fill the gaps. Each number from the given collection can be used at most once.

Your task is to determine such way of filling gaps that the longest increasing subsequence in the formed array has a maximum size.

Input

The first line contains a single integer n — the length of the array (1 ≤ n ≤ 105).

The second line contains n space-separated integers — the elements of the sequence. A gap is marked as "-1". The elements that are not gaps are positive integers not exceeding 109. It is guaranteed that the sequence contains 0 ≤ k ≤ 1000 gaps.

The third line contains a single positive integer m — the number of elements to fill the gaps (k ≤ m ≤ 105).

The fourth line contains m positive integers — the numbers to fill gaps. Each number is a positive integer not exceeding 109. Some numbers may be equal. 

Output

Print n space-separated numbers in a single line — the resulting sequence. If there are multiple possible answers, print any of them.

Examples

Input

3
1 2 3
1
10


Output

1 2 3 


Input

3
1 -1 3
3
1 2 3


Output

1 2 3 


Input

2
-1 2
2
2 4


Output

2 2 


Input

3
-1 -1 -1
5
1 1 1 1 2


Output

1 1 2 


Input

4
-1 -1 -1 2
4
1 1 2 2


Output

1 2 1 2 

Note

In the first sample there are no gaps, so the correct answer is the initial sequence.

In the second sample there is only one way to get an increasing subsequence of length 3.

In the third sample answer "4 2" would also be correct. Note that only strictly increasing subsequences are considered.

In the fifth sample the answer "1 1 1 2" is not considered correct, as number 1 can be used in replacing only two times.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / abs1(a) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitnum(long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
inline int bitmaxl(long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
  if (mod == -1) mod = 1000000007;
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
const int maxn = 300100;
int arr[maxn];
int addnum[maxn];
int n, nad;
struct tree_array {
  pair<int, int> num[1 << 18];
  int n, bigwei;
  void init(int nn = 1 << 18) {
    n = nn;
    while (lowb(nn) != nn) nn -= lowb(nn);
    bigwei = nn;
    n = bigwei * 2;
    for (int i = 0; i < n; i++) {
      num[i] = make_pair(0, -1);
    }
  }
  void upd(int no, pair<int, int> add) {
    while (no <= n) {
      num[no] = max(add, num[no]);
      no += lowb(no);
    }
  }
  pair<int, int> que(int no) {
    pair<int, int> ans = make_pair(0, -1);
    while (no) {
      ans = max(ans, num[no]);
      no -= lowb(no);
    }
    return ans;
  }
};
tree_array ta;
int lastcan[maxn * 2], lastcan1[maxn];
int val[maxn], val1[maxn];
pair<int, int> rval[maxn];
int trans[maxn], ltrans;
int used[maxn];
int get(int no) {
  if (no < n) return val[no];
  return val1[no - n];
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d", &n);
  ltrans = 0;
  for (int i = 0; i < n; i++) {
    scanf("%d", arr + i);
    trans[ltrans++] = arr[i];
  }
  scanf("%d", &nad);
  for (int i = 0; i < nad; i++) {
    scanf("%d", addnum + i);
    trans[ltrans++] = addnum[i];
  }
  sort(addnum, addnum + nad);
  sort(trans, trans + ltrans);
  ltrans = unique(trans, trans + ltrans) - trans;
  for (int i = 0; i < n; i++)
    if (arr[i] != -1) arr[i] = find(arr[i], trans, ltrans) + 3;
  for (int i = 0; i < nad; i++) addnum[i] = find(addnum[i], trans, ltrans) + 3;
  memset(lastcan1, -1, sizeof(lastcan1));
  ta.init(ltrans + 10);
  for (int i = 0; i < n; i++) {
    if (arr[i] == -1) {
      for (int link = -1, j = 0; j < nad; j++) {
        while (addnum[link + 1] < addnum[j]) link++;
        if (link == -1)
          rval[j] = make_pair(1, -1);
        else
          rval[j] = make_pair(val1[link] + 1, lastcan1[link]);
      }
      pair<int, int> temp = make_pair(0, -1);
      int rlink = 0;
      for (int j = 0; j < nad; j++) {
        while (rlink < addnum[j] - 1) {
          rlink++;
          temp = max(temp, ta.num[rlink]);
        }
        if (temp.first + 1 > val1[j]) {
          val1[j] = temp.first + 1;
          lastcan1[j] = temp.second;
        }
        if (rval[j].first > val1[j]) {
          val1[j] = rval[j].first;
          lastcan1[j] = rval[j].second;
        }
      }
    } else {
      pair<int, int> temp = ta.que(arr[i] - 1);
      temp.first++;
      int loc = find(arr[i] - 1, addnum, nad, 1, 0);
      if (loc != -1) {
        if (temp.first < val1[loc] + 1) {
          temp.first = val1[loc] + 1;
          temp.second = lastcan1[loc];
        }
      }
      val[i] = temp.first;
      lastcan[i] = temp.second;
      temp.second = i;
      ta.upd(arr[i], temp);
    }
  }
  int be = 0;
  for (int i = 0; i < n; i++)
    if (val[i] > val[be]) be = i;
  for (int i = 0; i < nad; i++)
    if (val1[i] > get(be)) be = i + n;
  for (int i = 0; i < n; i++)
    if (arr[i] >= 3) {
      assert(trans[arr[i] - 3] != -1);
    }
  int link = nad - 1;
  int last = 1000000007;
  if (be < n) last = arr[be];
  for (int i = 0; i < nad; i++) {
    lastcan[i + n] = lastcan1[i];
    val[i + n] = val1[i];
  }
  for (; be >= 0; be = lastcan[be]) {
    int nxt;
    if (lastcan[be] == -1)
      nxt = 0;
    else
      nxt = arr[lastcan[be]];
    while (link >= 0 && addnum[link] >= last) link--;
    for (int j = be; j > lastcan[be]; j--)
      if (arr[j] == -1) {
        while (link >= 0 && addnum[link] >= last) link--;
        if (link >= 0 && addnum[link] > nxt) {
          arr[j] = addnum[link];
          used[link] = 1;
          last = addnum[link];
          link--;
        }
      }
    last = nxt;
  }
  link = 0;
  for (int i = 0; i < n; i++)
    if (arr[i] == -1) {
      while (used[link]) link++;
      arr[i] = addnum[link];
      used[link] = 1;
    }
  for (int i = 0; i < n; i++) {
    cout << trans[arr[i] - 3] << ' ';
  }
  cout << endl;
  return 0;
}

```