Let's define the sum of two permutations p and q of numbers 0, 1, ..., (n - 1) as permutation [Image], where Perm(x) is the x-th lexicographically permutation of numbers 0, 1, ..., (n - 1) (counting from zero), and Ord(p) is the number of permutation p in the lexicographical order.

For example, Perm(0) = (0, 1, ..., n - 2, n - 1), Perm(n! - 1) = (n - 1, n - 2, ..., 1, 0)

Misha has two permutations, p and q. Your task is to find their sum.

Permutation a = (a_0, a_1, ..., a_{n} - 1) is called to be lexicographically smaller than permutation b = (b_0, b_1, ..., b_{n} - 1), if for some k following conditions hold: a_0 = b_0, a_1 = b_1, ..., a_{k} - 1 = b_{k} - 1, a_{k} < b_{k}.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 200 000).

The second line contains n distinct integers from 0 to n - 1, separated by a space, forming permutation p.

The third line contains n distinct integers from 0 to n - 1, separated by spaces, forming permutation q.


-----Output-----

Print n distinct integers from 0 to n - 1, forming the sum of the given permutations. Separate the numbers by spaces.


-----Examples-----
Input
2
0 1
0 1

Output
0 1

Input
2
0 1
1 0

Output
1 0

Input
3
1 2 0
2 1 0

Output
1 0 2



-----Note-----

Permutations of numbers from 0 to 1 in the lexicographical order: (0, 1), (1, 0).

In the first sample Ord(p) = 0 and Ord(q) = 0, so the answer is $\operatorname{Perm}((0 + 0) \operatorname{mod} 2) = \operatorname{Perm}(0) =(0,1)$.

In the second sample Ord(p) = 0 and Ord(q) = 1, so the answer is $\operatorname{Perm}((0 + 1) \operatorname{mod} 2) = \operatorname{Perm}(1) =(1,0)$.

Permutations of numbers from 0 to 2 in the lexicographical order: (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0).

In the third sample Ord(p) = 3 and Ord(q) = 5, so the answer is $\operatorname{Perm}((3 + 5) \operatorname{mod} 6) = \operatorname{Perm}(2) =(1,0,2)$.

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
import sys

class SegmTree:

	def __init__(self, array=None):
		size = len(array)
		N = 1
		while N < size:
			N <<= 1
		self.N = N
		self.tree = [0] * (2 * self.N)
		for i in range(size):
			self.tree[i + self.N] = array[i]
		self.build()

	def build(self):
		for i in range(self.N - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def add(self, i, value=1):
		i += self.N
		while i > 0:
			self.tree[i] += value
			i >>= 1

	def get_sum(self, l, r):
		N = self.N
		l += N
		r += N
		result = 0
		while l < r:
			if l & 1:
				result += self.tree[l]
				l += 1
			if r & 1:
				r -= 1
				result += self.tree[r]
			l >>= 1
			r >>= 1
		return result

	def find_kth_nonzero(self, k):
		i = 1
		if k < 1 or k > self.tree[1]:
			return -1
		while i < self.N:
			i <<= 1
			if self.tree[i] < k:
				k -= self.tree[i]
				i |= 1
		return i - self.N
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
ord_p = []
ord_q = []
st = SegmTree([1] * n)
for (i, val) in enumerate(p):
	ord_p.append(st.get_sum(0, val))
	st.add(val, -1)
st = SegmTree([1] * n)
for (i, val) in enumerate(q):
	ord_q.append(st.get_sum(0, val))
	st.add(val, -1)
transfer = 0
for i in range(n - 1, -1, -1):
	radix = n - i
	ord_p[i] = ord_p[i] + ord_q[i] + transfer
	if ord_p[i] < radix:
		transfer = 0
	else:
		transfer = 1
		ord_p[i] -= radix
st = SegmTree([1] * n)
for i in range(n):
	k = ord_p[i] + 1
	ord_q[i] = st.find_kth_nonzero(k)
	st.add(ord_q[i], -1)
print(*ord_q)


def sum(BIT, i):
	s = 0
	while i > 0:
		s += BIT[i]
		i -= i & -i
	return s

def update(BIT, i, v):
	while i < len(BIT):
		BIT[i] += v
		i += i & -i

def find(fen, k):
	curr = 0
	ans = 0
	prevsum = 0
	for i in range(19, -1, -1):
		if curr + (1 << i) < n and fen[curr + (1 << i)] + prevsum < k:
			ans = curr + (1 << i)
			curr = ans
			prevsum += fen[curr]
	return ans + 1

def Rank(x, BIT):
	return sum(BIT, x)
n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
factp = []
factq = []
BIT = [0] * (n + 1)
for j in range(n):
	update(BIT, j + 1, 1)
for val in p:
	factp.append(Rank(val + 1, BIT) - 1)
	update(BIT, val + 1, -1)
BIT = [0] * (n + 1)
for j in range(n):
	update(BIT, j + 1, 1)
for val in q:
	factq.append(Rank(val + 1, BIT) - 1)
	update(BIT, val + 1, -1)
carry = 0
for i in range(n - 1, -1, -1):
	radix = n - i
	factp[i] = factp[i] + factq[i] + carry
	if factp[i] < radix:
		carry = 0
	else:
		carry = 1
		factp[i] -= radix
BIT = [0] * (n + 1)
for j in range(n):
	update(BIT, j + 1, 1)
res = []
for i in range(n):
	k = factp[i] + 1
	res.append(find(BIT, k) - 1)
	update(BIT, res[-1] + 1, -1)
print(*res)