An array of integers $p_{1},p_{2}, \ldots,p_{n}$ is called a permutation if it contains each number from $1$ to $n$ exactly once. For example, the following arrays are permutations: $[3,1,2], [1], [1,2,3,4,5]$ and $[4,3,1,2]$. The following arrays are not permutations: $[2], [1,1], [2,3,4]$.

There is a hidden permutation of length $n$.

For each index $i$, you are given $s_{i}$, which equals to the sum of all $p_{j}$ such that $j < i$ and $p_{j} < p_{i}$. In other words, $s_i$ is the sum of elements before the $i$-th element that are smaller than the $i$-th element.

Your task is to restore the permutation.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^{5}$) — the size of the permutation.

The second line contains $n$ integers $s_{1}, s_{2}, \ldots, s_{n}$ ($0 \le s_{i} \le \frac{n(n-1)}{2}$).

It is guaranteed that the array $s$ corresponds to a valid permutation of length $n$.


-----Output-----

Print $n$ integers $p_{1}, p_{2}, \ldots, p_{n}$ — the elements of the restored permutation. We can show that the answer is always unique.


-----Examples-----
Input
3
0 0 0

Output
3 2 1

Input
2
0 1

Output
1 2

Input
5
0 1 1 1 10

Output
1 4 3 2 5



-----Note-----

In the first example for each $i$ there is no index $j$ satisfying both conditions, hence $s_i$ are always $0$.

In the second example for $i = 2$ it happens that $j = 1$ satisfies the conditions, so $s_2 = p_1$.

In the third example for $i = 2, 3, 4$ only $j = 1$ satisfies the conditions, so $s_2 = s_3 = s_4 = 1$. For $i = 5$ all $j = 1, 2, 3, 4$ are possible, so $s_5 = p_1 + p_2 + p_3 + p_4 = 10$.

Source: codeforces | Difficulty: HARD
Tags: Sorting

Data structures

Implementation

Greedy algorithms


Solutions:
import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
n = int(input())
l = list(map(int, input().split()))
f = [i for i in range(1, n + 1)]
s = SegmentTree(f)
ans = [0] * n
for i in range(n - 1, -1, -1):
	st = 1
	end = n
	while st <= end:
		mid = (st + end) // 2
		su = s.query(0, mid - 2)
		if su == l[i]:
			an = mid
			st = mid + 1
		elif su < l[i]:
			st = mid + 1
		else:
			end = mid - 1
	ans[i] = an
	s.__setitem__(an - 1, 0)
print(*ans, sep=' ')


from sys import setrecursionlimit as SRL, stdin
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : map(int, rd().strip().split())
n = int(rd())
bit = [0] * 200005

def add(x, val):
	while x <= n:
		bit[x] += val
		x += x & -x

def query(x):
	num = 0
	for i in range(30, -1, -1):
		if num + (1 << i) <= n and bit[num + (1 << i)] <= x:
			x -= bit[num + (1 << i)]
			num += 1 << i
	return num + 1
for i in range(1, n + 1):
	add(i, i)
s = list(rrd())
ans = []
for i in range(len(s) - 1, -1, -1):
	q = query(s[i])
	ans.append(q)
	add(q, -q)
ans = ans[::-1]
print(*ans)


from sys import stdin, stdout

class Tree(object):

	def __init__(self, n):
		self.tree = [0] * (4 * n + 10)
		self.b = [0] * (n + 10)
		self.a = list(map(int, stdin.readline().split()))
		self.n = n

	def update(self, L, C, l, r, rt):
		if l == r:
			self.tree[rt] += C
			return
		mid = (l + r) // 2
		if L <= mid:
			self.update(L, C, l, mid, rt << 1)
		else:
			self.update(L, C, mid + 1, r, rt << 1 | 1)
		self.tree[rt] = self.tree[rt << 1] + self.tree[rt << 1 | 1]

	def query(self, s, l, r, rt):
		if l == r:
			return l
		mid = (l + r) // 2
		if self.tree[rt << 1] > s:
			return self.query(s, l, mid, rt << 1)
		else:
			return self.query(s - self.tree[rt << 1], mid + 1, r, rt << 1 | 1)

	def slove(self):
		for i in range(n):
			self.update(i + 1, i + 1, 1, n, 1)
		for i in range(n, 0, -1):
			self.b[i] = self.query(self.a[i - 1], 1, n, 1)
			self.update(self.b[i], -self.b[i], 1, n, 1)
		for i in range(n):
			stdout.write('%d ' % self.b[i + 1])
n = int(stdin.readline())
seg = Tree(n)
seg.slove()


from sys import stdin, stdout
input = stdin.readline

class BIT:

	def __init__(self, nums):
		self.nums = [0] * len(nums)
		for (i, x) in enumerate(nums):
			if i == 0:
				continue
			self.update(i, x)

	def low_bit(self, x):
		return x & -x

	def update(self, i, diff):
		while i < len(self.nums):
			self.nums[i] += diff
			i += self.low_bit(i)

	def prefix_sum(self, i):
		ret = 0
		while i != 0:
			ret += self.nums[i]
			i -= self.low_bit(i)
		return ret

	def search(self, x):
		(cur_index, cur_sum) = (0, 0)
		delta = len(self.nums) - 1
		while delta - self.low_bit(delta):
			delta -= self.low_bit(delta)
		while delta:
			m = cur_index + delta
			if m < len(self.nums):
				sm = cur_sum + self.nums[m]
				if sm <= x:
					(cur_index, cur_sum) = (m, sm)
			delta //= 2
		return cur_index + 1
n = int(input())
bit = BIT(range(n + 1))
ans = [0 for _ in range(n)]
nums = list(map(int, input().split()))
for i in range(n - 1, -1, -1):
	index = bit.search(nums[i])
	bit.update(index, -index)
	ans[i] = index
print(*ans)


from sys import stdin, stdout
from collections import defaultdict
from collections import deque
import math
import copy
N = int(input())
arr = [int(x) for x in stdin.readline().split()]
bit = [0] * (N + 1)
series = [0] + [x for x in range(N)]

def lowbit(x):
	return x & -x

def update(idx, delta):
	while idx <= N:
		bit[idx] += delta
		idx += lowbit(idx)

def query(x):
	s = 0
	while x > 0:
		s += bit[x]
		x -= lowbit(x)
	return s
for i in range(1, N + 1):
	bit[i] += series[i]
	y = i + lowbit(i)
	if y <= N:
		series[y] += series[i]
visited = [0] * (N + 1)
ans = [0] * N
for i in range(N - 1, -1, -1):
	left = 1
	right = N
	target = arr[i]
	while left <= right:
		mid = (left + right) // 2
		q = query(mid)
		if q < target:
			left = mid + 1
		elif q > target:
			right = mid - 1
		elif visited[mid] == 1:
			left = mid + 1
		else:
			visited[mid] = 1
			ans[i] = mid
			break
	update(mid + 1, -mid)
print(*ans)


def sumsegtree(l, seg, st, en, x):
	if st == en:
		seg[x] = l[st]
	else:
		mid = st + en >> 1
		sumsegtree(l, seg, st, mid, 2 * x)
		sumsegtree(l, seg, mid + 1, en, 2 * x + 1)
		seg[x] = seg[2 * x] + seg[2 * x + 1]

def query(seg, st, en, val, x):
	if st == en:
		return seg[x]
	mid = st + en >> 1
	if seg[2 * x] >= val:
		return query(seg, st, mid, val, 2 * x)
	return query(seg, mid + 1, en, val - seg[2 * x], 2 * x + 1)

def upd(seg, st, en, ind, val, x):
	if st == en:
		seg[x] = val
		return
	mid = st + en >> 1
	if mid >= ind:
		upd(seg, st, mid, ind, val, 2 * x)
	else:
		upd(seg, mid + 1, en, ind, val, 2 * x + 1)
	seg[x] = seg[2 * x] + seg[2 * x + 1]
n = int(input())
l = list(map(int, range(1, n + 1)))
s = [0] * n
p = list(map(int, input().split()))
seg = ['#'] * (n << 2)
sumsegtree(l, seg, 0, len(l) - 1, 1)
for i in range(len(p) - 1, -1, -1):
	s[i] = query(seg, 1, n, p[i] + 1, 1)
	upd(seg, 1, n, s[i], 0, 1)
print(*s)


import sys
input = sys.stdin.readline
nn = 18
bit = [0] * (2 ** nn + 1)

def addbit(i, x):
	while i <= 2 ** nn:
		bit[i] += x
		i += i & -i

def getsum(i):
	ret = 0
	while i != 0:
		ret += bit[i]
		i -= i & -i
	return ret

def searchbit(x):
	(l, sl) = (0, 0)
	d = 2 ** (nn - 1)
	while d:
		m = l + d
		sm = sl + bit[m]
		if sm <= x:
			(l, sl) = (m, sm)
		d //= 2
	return l + 1
n = int(input())
l = list(map(int, input().split()))
for i in range(1, n + 1):
	addbit(i, i)
ans = [0 for _ in range(n)]
for i in range(n - 1, -1, -1):
	a = searchbit(l[i])
	addbit(a, -a)
	ans[i] = a
print(*ans)


def sum_number(n, j):
	j[0] = 0
	j[1] = 0
	for i in range(2, n + 1):
		j[i] = j[i - 1] + (i - 1)
	return j
po = int(input())
l = [0] * (po + 1)
l1 = [int(i) for i in input().split()]

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

def updatebit(BITTree, n, i, v):
	while i <= n:
		BITTree[i] += v
		i += i & -i
for i in range(1, po + 1):
	updatebit(l, po, i, i)
output = [0] * po
for i in range(po - 1, -1, -1):
	min_ = 0
	max_ = po
	k = l1[i]
	while True:
		x = (min_ + max_ + 1) // 2
		if getsum(l, x) > k:
			if getsum(l, x - 1) == k:
				output[i] = x
				break
			else:
				max_ = x
		else:
			min_ = x
	updatebit(l, po, x, -x)
print(*output)


import sys
input = sys.stdin.readline

class SegTree(object):

	def __init__(self, n, arr):
		self.n = n
		self.arr = arr
		self.tree = [0 for i in range(2 * n)]

	def construct(self):
		for i in range(self.n):
			self.tree[n + i] = self.arr[i]
		for i in range(n - 1, 0, -1):
			self.tree[i] = self.function(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, index, value):
		start = index + self.n
		self.tree[start] = value
		while start > 0:
			start = start // 2
			self.tree[start] = self.function(self.tree[2 * start], self.tree[2 * start + 1])

	def calc(self, low, high):
		low += self.n
		high += self.n
		ans = 0
		while low < high:
			if low % 2:
				ans = self.function(ans, self.tree[low])
				low += 1
			if high % 2:
				high -= 1
				ans = self.function(ans, self.tree[high])
			low = low // 2
			high = high // 2
		return ans

	def function(self, a, b):
		return a + b

def find(num):
	low = 0
	high = n - 1
	while low < high:
		mid = (low + high) // 2
		if st.calc(0, mid + 1) > num:
			high = mid - 1
		else:
			low = mid + 1
	if st.calc(0, low + 1) > num:
		return low
	else:
		return low + 1
n = int(input())
a = list(map(int, input().split()))
arr = [i for i in range(1, n + 1)]
st = SegTree(n, arr)
st.construct()
ans = [-1] * n
for i in range(n - 1, -1, -1):
	ind = find(a[i])
	ans[i] = arr[ind]
	st.update(ind, 0)
print(*ans)


n = int(input())
P = [int(i) for i in input().split()]
import math
import bisect
n_max = 2 * 10 ** 5
nn = int(math.log2(n_max)) + 1
BIT = [0] * (2 ** nn + 1)

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

def bitadd(BIT, i, x):
	if i <= 0:
		return True
	else:
		while i <= 2 ** nn:
			BIT[i] += x
			i += i & -i
		return BIT

def bitlowerbound(BIT, s):
	if s <= 0:
		return 0
	else:
		ret = 0
		k = 2 ** nn
		while k > 0:
			if k + ret <= 2 ** nn and BIT[k + ret] < s:
				s -= BIT[k + ret]
				ret += k
			k //= 2
		return ret + 1
for i in range(n_max):
	bitadd(BIT, i + 1, i + 1)
Ans = []
for i in reversed(range(n)):
	p = P[i]
	ans = bitlowerbound(BIT, p + 1)
	Ans.append(ans)
	bitadd(BIT, ans, -ans)
Ans = Ans[::-1]
print(*Ans)


from operator import add

class Stree:

	def __init__(self, f, n, default, init_data):
		self.ln = 2 ** (n - 1).bit_length()
		self.data = [default] * (self.ln * 2)
		self.f = f
		for (i, d) in init_data.items():
			self.data[self.ln + i] = d
		for j in range(self.ln - 1, 0, -1):
			self.data[j] = f(self.data[j * 2], self.data[j * 2 + 1])

	def update(self, i, a):
		p = self.ln + i
		self.data[p] = a
		while p > 1:
			p = p // 2
			self.data[p] = self.f(self.data[p * 2], self.data[p * 2 + 1])

	def get(self, i, j):

		def _get(l, r, p):
			if i <= l and j >= r:
				return self.data[p]
			else:
				m = (l + r) // 2
				if j <= m:
					return _get(l, m, p * 2)
				elif i >= m:
					return _get(m, r, p * 2 + 1)
				else:
					return self.f(_get(l, m, p * 2), _get(m, r, p * 2 + 1))
		return _get(0, self.ln, 1)

	def find_value(self, v):

		def _find_value(l, r, p, v):
			if r == l + 1:
				return l
			elif self.data[p * 2] <= v:
				return _find_value((l + r) // 2, r, p * 2 + 1, v - self.data[p * 2])
			else:
				return _find_value(l, (l + r) // 2, p * 2, v)
		return _find_value(0, self.ln, 1, v)

def main():
	n = int(input())
	sums = {i: i for i in range(n + 1)}
	stree = Stree(add, n + 1, 0, sums)
	ss = list(map(int, input().split()))
	ss.reverse()
	pp = []
	for s in ss:
		sval = stree.find_value(s)
		pp.append(sval)
		stree.update(sval, 0)
	print(*reversed(pp))

def __starting_point():
	main()
__starting_point()


class segTree:

	def __init__(self, n):
		self.t = [0] * (n << 2)

	def update(self, node, l, r, index, value):
		if l == r:
			self.t[node] = value
			return
		mid = l + r >> 1
		if index <= mid:
			self.update(node * 2, l, mid, index, value)
		else:
			self.update(node * 2 + 1, mid + 1, r, index, value)
		self.t[node] = self.t[node * 2] + self.t[node * 2 + 1]

	def query(self, node, l, r, value):
		if l == r:
			return self.t[node]
		mid = l + r >> 1
		if self.t[node * 2] >= value:
			return self.query(node * 2, l, mid, value)
		return self.query(node * 2 + 1, mid + 1, r, value - self.t[node * 2])

def do():
	n = int(input())
	nums = [int(i) for i in input().split(' ')]
	res = [0] * n
	weightTree = segTree(n)
	for i in range(1, n + 1):
		weightTree.update(1, 1, n, i, i)
	for i in range(n - 1, -1, -1):
		res[i] = weightTree.query(1, 1, n, nums[i] + 1)
		weightTree.update(1, 1, n, res[i], 0)
	return ' '.join([str(c) for c in res])
print(do())


_ = input()
x = [int(i) for i in input().split()]
res = []
from math import log

class SegmentTree(object):

	def __init__(self, nums):
		self.arr = nums
		self.l = len(nums)
		self.tree = [0] * self.l + nums
		for i in range(self.l - 1, 0, -1):
			self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

	def update(self, i, val):
		n = self.l + i
		self.tree[n] = val
		while n > 1:
			self.tree[n >> 1] = self.tree[n] + self.tree[n ^ 1]
			n >>= 1

	def query(self, i, j):
		m = self.l + i
		n = self.l + j
		res = 0
		while m <= n:
			if m & 1:
				res += self.tree[m]
				m += 1
			m >>= 1
			if n & 1 == 0:
				res += self.tree[n]
				n -= 1
			n >>= 1
		return res
tree = SegmentTree(list(range(1, len(x) + 1)))
org = len(x)
while x:
	q = x.pop()
	lo = 0
	hi = org - 1
	while lo < hi:
		mid = (lo + hi) // 2
		sm = tree.query(0, mid)
		if sm > q:
			hi = mid
		else:
			lo = mid + 1
	idx = tree.arr[lo]
	tree.update(lo, 0)
	res.append(idx)
print(' '.join((str(i) for i in res[::-1])))


import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
BIT = [0] * (n + 1)

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

def getvalue(v):
	ANS = 0
	while v != 0:
		ANS += BIT[v]
		v -= v & -v
	return ANS
for i in range(1, n + 1):
	update(i, i)
ANS = [-1] * n
for i in range(n - 1, -1, -1):
	MIN = 0
	MAX = n
	k = A[i]
	while True:
		x = (MIN + MAX + 1) // 2
		if getvalue(x) > k:
			if getvalue(x - 1) == k:
				ANS[i] = x
				break
			else:
				MAX = x
		else:
			MIN = x
	update(x, -x)
print(*ANS)


import sys
input = sys.stdin.readline
n = int(input())
s = list(map(int, input().split()))
BIT = [0] * (n + 1)

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

def get_sum(i):
	res = 0
	while i > 0:
		res += BIT[i]
		i -= i & -i
	return res
for i in range(1, n + 1):
	update(i, i)
ans = [-1] * n
for i in range(n)[::-1]:
	l = 0
	r = n
	ss = s[i]
	while True:
		mid = (l + r + 1) // 2
		if get_sum(mid) > ss:
			if get_sum(mid - 1) == ss:
				ans[i] = mid
				break
			else:
				r = mid
		else:
			l = mid
	update(mid, -mid)
print(*ans)


def update(x, val):
	while x <= n:
		BIT[x] += val
		x += x & -x

def query(x):
	s = 0
	while x > 0:
		s = s + BIT[x]
		x -= x & -x
	return s
n = int(input())
BIT = [0] * (n + 1)
for i in range(1, n + 1):
	update(i, i)
arr = list(map(int, input().split()))
answers = [0] * n
for i in range(n - 1, -1, -1):
	lol = arr[i]
	low = 0
	fjf = 0
	high = n
	while True:
		mid = (high + low + 1) // 2
		j = query(mid)
		if j > lol:
			if query(mid - 1) == lol:
				answers[i] = mid
				update(mid, -mid)
				break
			else:
				high = mid
		else:
			low = mid
print(*answers)


NN = 18
BIT = [0] * (2 ** NN + 1)

def addbit(i, x):
	while i <= 2 ** NN:
		BIT[i] += x
		i += i & -i

def getsum(i):
	ret = 0
	while i != 0:
		ret += BIT[i]
		i -= i & -i
	return ret

def searchbit(x):
	(l, sl) = (0, 0)
	d = 2 ** (NN - 1)
	while d:
		m = l + d
		sm = sl + BIT[m]
		if sm <= x:
			(l, sl) = (m, sm)
		d //= 2
	return l
N = int(input())
A = [int(a) for a in input().split()]
for i in range(1, N + 1):
	addbit(i, i)
ANS = []
for s in A[::-1]:
	a = searchbit(s) + 1
	addbit(a, -a)
	ANS.append(a)
print(*ANS[::-1])


class DualBIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def get(self, i):
		i = i + 1
		s = 0
		while i <= self.n:
			s += self.bit[i]
			i += i & -i
		return s

	def _add(self, i, x):
		while i > 0:
			self.bit[i] += x
			i -= i & -i

	def add(self, i, j, x):
		self._add(j, x)
		self._add(i, -x)
n = int(input())
a = list(map(int, input().split()))
bit = DualBIT(n + 3)
for i in range(1, n + 1):
	bit.add(i + 1, n + 1, i)
li = []
flag = False
while True:
	if not a:
		break
	ok = n + 1
	ng = 0
	num = a[-1]
	if num == 0 and (not flag):
		flag = True
		bit.add(1, n + 2, -1)
		li.append(1)
		del a[-1]
		continue
	while abs(ok - ng) > 1:
		mid = (ok + ng) // 2
		if bit.get(mid) > num:
			ok = mid
		else:
			ng = mid
	tmp = ok - 1
	bit.add(ok, n + 2, -tmp)
	li.append(tmp)
	del a[-1]
print(*li[::-1])


class FTree:

	def __init__(self, f):
		self.n = len(f)
		self.ft = [0] * (self.n + 1)
		for i in range(1, self.n + 1):
			self.ft[i] += f[i - 1]
			if i + self.lsone(i) <= self.n:
				self.ft[i + self.lsone(i)] += self.ft[i]

	def lsone(self, s):
		return s & -s

	def query(self, i, j):
		if i > 1:
			return self.query(1, j) - self.query(1, i - 1)
		s = 0
		while j > 0:
			s += self.ft[j]
			j -= self.lsone(j)
		return s

	def update(self, i, v):
		while i <= self.n:
			self.ft[i] += v
			i += self.lsone(i)

	def select(self, k):
		lo = 1
		hi = self.n
		for i in range(19):
			mid = (lo + hi) // 2
			if self.query(1, mid) < k:
				lo = mid
			else:
				hi = mid
		return hi
n = int(input())
data = [int(i) for i in input().split()]
ft = FTree(list(range(1, n + 1)))
ans = [''] * n
for i in range(n - 1, -1, -1):
	val = data[i]
	ind = ft.select(val + 1)
	ans[i] = str(ind)
	ft.update(ind, -ind)
print(' '.join(ans))


from sys import stdin, stdout

def update(L, C, l, r, rt):
	if l == r:
		tree[rt] += C
		return
	mid = (l + r) // 2
	if L <= mid:
		update(L, C, l, mid, rt << 1)
	else:
		update(L, C, mid + 1, r, rt << 1 | 1)
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]

def query(s, l, r, rt):
	if l == r:
		return l
	mid = (l + r) // 2
	if tree[rt << 1] > s:
		return query(s, l, mid, rt << 1)
	else:
		return query(s - tree[rt << 1], mid + 1, r, rt << 1 | 1)
tree = [0] * 800005
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
for i in range(n):
	update(i + 1, i + 1, 1, n, 1)
b = [0] * 200005
for i in range(n, 0, -1):
	b[i] = query(a[i - 1], 1, n, 1)
	update(b[i], -b[i], 1, n, 1)
for i in range(n):
	stdout.write('%d ' % b[i + 1])