A permutation of size $n$ is an array of size $n$ such that each integer from $1$ to $n$ occurs exactly once in this array. An inversion in a permutation $p$ is a pair of indices $(i, j)$ such that $i > j$ and $a_i < a_j$. For example, a permutation $[4, 1, 3, 2]$ contains $4$ inversions: $(2, 1)$, $(3, 1)$, $(4, 1)$, $(4, 3)$.

You are given a permutation $p$ of size $n$. However, the numbers on some positions are replaced by $-1$. Let the valid permutation be such a replacement of $-1$ in this sequence back to numbers from $1$ to $n$ in such a way that the resulting sequence is a permutation of size $n$.

The given sequence was turned into a valid permutation randomly with the equal probability of getting each valid permutation.

Calculate the expected total number of inversions in the resulting valid permutation.

It can be shown that it is in the form of $\frac{P}{Q}$ where $P$ and $Q$ are non-negative integers and $Q \ne 0$. Report the value of $P \cdot Q^{-1} \pmod {998244353}$.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the sequence.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($-1 \le p_i \le n$, $p_i \ne 0$) — the initial sequence.

It is guaranteed that all elements not equal to $-1$ are pairwise distinct.


-----Output-----

Print a single integer — the expected total number of inversions in the resulting valid permutation.

It can be shown that it is in the form of $\frac{P}{Q}$ where $P$ and $Q$ are non-negative integers and $Q \ne 0$. Report the value of $P \cdot Q^{-1} \pmod {998244353}$.


-----Examples-----
Input
3
3 -1 -1

Output
499122179

Input
2
1 2

Output
0

Input
2
-1 -1

Output
499122177



-----Note-----

In the first example two resulting valid permutations are possible:

  $[3, 1, 2]$ — $2$ inversions;  $[3, 2, 1]$ — $3$ inversions. 

The expected value is $\frac{2 \cdot 1 + 3 \cdot 1}{2} = 2.5$.

In the second example no $-1$ are present, thus the only valid permutation is possible — the given one. It has $0$ inversions.

In the third example there are two resulting valid permutations — one with $0$ inversions and one with $1$ inversion.

Difficulty: HARD
Tags: Dynamic programming

Mathematics

Probability
Skill types: Dynamic programming
Expected Time Complexity: O(NLOG(N))

Starter code:

Solutions:
def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	if n == 1:
		return 0
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=None):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class Matrix:
	mod = 10 ** 9 + 7

	def set_mod(m):
		Matrix.mod = m

	def __init__(self, L):
		self.row = len(L)
		self.column = len(L[0])
		self._matrix = L
		for i in range(self.row):
			for j in range(self.column):
				self._matrix[i][j] %= Matrix.mod

	def __getitem__(self, item):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		return self._matrix[i][j]

	def __setitem__(self, item, val):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		self._matrix[i][j] = val

	def __add__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] + other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __sub__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] - other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __mul__(self, other):
		if type(other) != int:
			if self.column != other.row:
				raise SizeError('sizes of matrixes are different')
			res = [[0 for j in range(other.column)] for i in range(self.row)]
			for i in range(self.row):
				for j in range(other.column):
					temp = 0
					for k in range(self.column):
						temp += self._matrix[i][k] * other._matrix[k][j]
					res[i][j] = temp % Matrix.mod
			return Matrix(res)
		else:
			n = other
			res = [[n * self._matrix[i][j] % Matrix.mod for j in range(self.column)] for i in range(self.row)]
			return Matrix(res)

	def __pow__(self, m):
		if self.column != self.row:
			raise MatrixPowError('the size of row must be the same as that of column')
		n = self.row
		res = Matrix([[int(i == j) for i in range(n)] for j in range(n)])
		while m:
			if m % 2 == 1:
				res = res * self
			self = self * self
			m //= 2
		return res

	def __str__(self):
		res = []
		for i in range(self.row):
			for j in range(self.column):
				res.append(str(self._matrix[i][j]))
				res.append(' ')
			res.append('\n')
		res = res[:len(res) - 1]
		return ''.join(res)

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1

def cmb(n, r, mod):
	if r < 0 or r > n:
		return 0
	r = min(r, n - r)
	return g1[n] * g2[r] % mod * g2[n - r] % mod
mod = 998244353
N = 2 * 10 ** 5
g1 = [1] * (N + 1)
g2 = [1] * (N + 1)
inverse = [1] * (N + 1)
for i in range(2, N + 1):
	g1[i] = g1[i - 1] * i % mod
	inverse[i] = -inverse[mod % i] * (mod // i) % mod
	g2[i] = g2[i - 1] * inverse[i] % mod
inverse[0] = 0
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import log, gcd
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
n = int(input())
p = li()
val = set([p[i] for i in range(n)])
fw = BIT(n)
cnt = 0
for i in range(1, n + 1):
	if i not in val:
		fw.update(i, 1)
		cnt += 1
res = 0
tmp = 0
for i in range(n):
	if p[i] != -1:
		tmp += fw.query(p[i])
	else:
		res += tmp * inverse[cnt]
		res %= mod
tmp = 0
for i in range(n - 1, -1, -1):
	if p[i] != -1:
		tmp += cnt - fw.query(p[i])
	else:
		res += tmp * inverse[cnt]
		res %= mod
res += cnt * (cnt - 1) * inverse[4]
res %= mod
fw = BIT(n)
cnt = 0
for i in range(n):
	if p[i] != -1:
		res += cnt - fw.query(p[i])
		cnt += 1
		fw.update(p[i], 1)
print(res % mod)


import sys
input = sys.stdin.readline
n = int(input())
P = list(map(int, input().split()))
mod = 998244353
INV = [None] * (n + 1)
for i in range(1, n + 1):
	INV[i] = pow(i, mod - 2, mod)
BLA = P.count(-1)
if BLA == 0 or BLA == 1:
	ANS = 0
else:
	LEFT = BLA * (BLA - 1) // 2 * INV[BLA] % mod
	AVEP = BLA * (BLA - 1) // 2 * pow(BLA - 1, mod - 2, mod)
	ANS = LEFT * AVEP % mod
y = 1
for i in range(BLA):
	y = y * (BLA - i) % mod
KOSUU = pow(y, mod - 2, mod)
BLALIST = [1] * (n + 1)
NONBLA = []
BLANUM = [0] * n
for i in range(n):
	if P[i] != -1:
		BLALIST[P[i]] = 0
		BLANUM[i] = BLANUM[i - 1]
		NONBLA.append(P[i])
	else:
		BLANUM[i] = BLANUM[i - 1] + 1
BLALIST[0] = 0
for i in range(1, n + 1):
	BLALIST[i] = BLALIST[i - 1] + BLALIST[i]
if BLA != 0:
	for i in range(n):
		if P[i] != -1:
			ANS = (ANS + (BLANUM[i] * (BLA - BLALIST[P[i]]) + (BLA - BLANUM[i]) * BLALIST[P[i]]) * INV[BLA]) % mod
A = NONBLA
if A == []:
	print(ANS)
	return
n = len(A)
MAXA = max(A)
MINA = min(A)
BIT = [0] * (MAXA - MINA + 2)
for i in range(n):
	bitobje = A[i] - MINA + 1
	x = bitobje
	while x != 0:
		ANS = (ANS - BIT[x]) % mod
		x -= x & -x
	x2 = MAXA - MINA + 1
	while x2 != 0:
		ANS = (ANS + BIT[x2]) % mod
		x2 -= x2 & -x2
	y = bitobje
	while y <= MAXA - MINA + 1:
		BIT[y] += 1
		y += y & -y
print(ANS)


def merge(a, b):
	inda = 0
	indb = 0
	lena = len(a)
	lenb = len(b)
	d = [a[-1] + b[-1] + 1000]
	a += d
	b += d
	c = []
	inversions = 0
	for i in range(lena + lenb):
		if a[inda] < b[indb]:
			c.append(a[inda])
			inda += 1
		else:
			c.append(b[indb])
			indb += 1
			inversions += lena - inda
	return (c, inversions)

def mergesort(a):
	if len(a) <= 1:
		return (a, 0)
	split = len(a) // 2
	b = a[:split]
	c = a[split:]
	d = mergesort(b)
	e = mergesort(c)
	f = merge(d[0], e[0])
	return (f[0], f[1] + d[1] + e[1])
n = int(input())
a = list(map(int, input().split()))
b = []
for guy in a:
	if guy != -1:
		b.append(guy)
invs = mergesort(b)[1]
negs = len(a) - len(b)
pairs = negs * (negs - 1) // 2
used = [0] * n
for guy in a:
	if guy != -1:
		used[guy - 1] += 1
unused = [0]
for i in range(n - 1):
	unused.append(unused[-1] + 1 - used[i])
negsseen = 0
mix = 0
for i in range(n):
	if a[i] == -1:
		negsseen += 1
	else:
		mix += unused[a[i] - 1] * (negs - negsseen) + negsseen * (negs - unused[a[i] - 1])
num = invs * 2 * negs + pairs * negs + mix * 2
denom = 2 * negs
if negs == 0:
	print(invs % 998244353)
else:
	for i in range(denom):
		if (998244353 * i + 1) % denom == 0:
			inv = (998244353 * i + 1) // denom
			break
	print(num * inv % 998244353)


MOD = 998244353

def power(x, n):
	ans = 1
	while n:
		if n & 1 == 1:
			ans = ans * x % MOD
		x = x * x % MOD
		n = n // 2
	return ans
n = int(input())
a = list(map(int, input().split()))
b = [0 for i in range(n + 1)]

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

def get(x):
	ans = 0
	while x:
		ans = ans + b[x]
		x = x - (x & -x)
	return ans
anss = 0
for i in range(n):
	if a[i] != -1:
		add(a[i], 1)
		anss = anss + get(n) - get(a[i])
anss = anss % MOD
total = 0
sur = [0] + [1 for i in range(n)]
for i in range(n):
	if a[i] == -1:
		total = total + 1
	else:
		sur[a[i]] = 0
if total == 0:
	print(anss)
	return
for i in range(1, n + 1):
	sur[i] = sur[i] + sur[i - 1]
dead = 0
ansa = 0
for i in range(n):
	if a[i] != -1:
		ansa = ansa + sur[a[i]] * (total - dead) + (sur[n] - sur[a[i]]) * dead
	else:
		dead = dead + 1
ans = (ansa * 4 + anss * 4 * total + total * total * (total - 1)) % MOD
ans = ans * power(4 * total, MOD - 2) % MOD
print(ans)


base = 998244353

def power(x, y):
	if y == 0:
		return 1
	t = power(x, y // 2)
	t = t * t % base
	if y % 2:
		t = t * x % base
	return t

def inverse(x):
	return power(x, base - 2)
ft = [0]
for i in range(0, 200000):
	ft.append(0)

def get(i):
	res = 0
	while i <= 200000:
		res += ft[i]
		i += i & -i
	return res

def update(i, x):
	while i:
		ft[i] += x
		i -= i & -i
n = int(input())
a = [0]
a += list(map(int, input().split()))
neg = [0]
non = [0]
for i in range(1, n + 1):
	non.append(0)
for i in range(1, n + 1):
	if a[i] != -1:
		non[a[i]] += 1
for i in range(1, n + 1):
	non[i] += non[i - 1]
for i in range(1, n + 1):
	if a[i] == -1:
		neg.append(neg[i - 1] + 1)
	else:
		neg.append(neg[i - 1])
m = neg[n]
ans = 0
for i in range(1, n + 1):
	if a[i] != -1:
		ans += get(a[i])
		update(a[i], 1)
fm = 1
fs = fm
for i in range(1, m + 1):
	fs = fm
	fm = fm * i % base
fs = fs * inverse(fm) % base
for i in range(1, n + 1):
	if a[i] != -1:
		less = a[i] - non[a[i]]
		more = m - less
		ans = (ans + neg[i] * more * fs) % base
		ans = (ans + (m - neg[i]) * less * fs) % base
ans = (ans + m * (m - 1) * inverse(4)) % base
print(ans)


n = int(input())
L = [int(x) for x in input().split()]
D = {}
J = []
S = []
T = [0] * (n + 1)
for i in range(n):
	if L[i] > 0:
		D[L[i]] = i
		J.append(L[i])
		T[i + 1] = T[i]
	else:
		T[i + 1] = T[i] + 1

def I(J):
	if len(J) <= 1:
		return (J, 0)
	else:
		a = J[:len(J) // 2]
		b = J[len(J) // 2:]
		(a, ai) = I(a)
		(b, bi) = I(b)
		c = []
		i = 0
		j = 0
		inversions = ai + bi
	while i < len(a) and j < len(b):
		if a[i] <= b[j]:
			c.append(a[i])
			i += 1
		else:
			c.append(b[j])
			j += 1
			inversions += len(a) - i
	c += a[i:]
	c += b[j:]
	return (c, inversions)
for i in range(1, n + 1):
	if not i in D:
		S.append(i)
total = len(S)
num = 1
denom = 1
if total > 0:
	themostimportantsum = 0
	for i in J:
		low = 0
		high = total - 1
		while high - low > 1:
			guess = (high + low) // 2
			if S[guess] > i:
				high = guess
			else:
				low = guess
		if S[low] > i:
			smaller = low
		elif S[high] > i:
			smaller = high
		else:
			smaller = high + 1
		themostimportantsum += T[D[i]] * (total - smaller) + (total - T[D[i]]) * smaller
		num = themostimportantsum + total
		denom = total
num = (denom * (total * (total - 1) // 2) + 2 * num) % 998244353
denom *= 2
if num == denom:
	if I(J)[1] == 0:
		print(0)
	else:
		print(I(J)[1] % 998244353)
else:
	num += denom * I(J)[1]
	print((num - denom) * pow(denom % 998244353, 998244351, 998244353) % 998244353)


K = 998244353

def mu(a, n):
	if n == 0:
		return 1
	q = mu(a, n // 2)
	if n % 2 == 0:
		return q * q % K
	return q * q % K * a % K
MAXN = 200005
dd = [0 for i in range(MAXN)]
p = [0 for i in range(MAXN)]
s = [0 for i in range(MAXN)]
a = [0 for i in range(MAXN)]
fen = [0 for i in range(MAXN)]

def add(u, v):
	i = u
	while i <= 200000:
		fen[i] += v
		i += i & -i

def get(u):
	res = 0
	i = u
	while i > 0:
		res += fen[i]
		i -= i & -i
	return res
n = int(input())
data = input().split()
cnt = 0
for i in range(1, n + 1):
	p[i] = int(data[i - 1])
	if p[i] > 0:
		dd[p[i]] = 1
	else:
		cnt += 1
for i in range(1, n + 1):
	if dd[i] == 0:
		s[i] = s[i - 1] + 1
	else:
		s[i] = s[i - 1]
cnt1 = 0
P = 0
den = mu(cnt, K - 2)
for i in range(1, n + 1):
	if p[i] == -1:
		cnt1 += 1
	else:
		u = cnt - cnt1
		P = (P + u * s[p[i]] % K * den % K) % K
		P = (P + cnt1 * (cnt - s[p[i]]) % K * den % K) % K
P = (P + cnt * (cnt - 1) * mu(4, K - 2)) % K
m = 0
for i in range(1, n + 1):
	if p[i] > 0:
		m += 1
		a[m] = p[i]
P1 = 0
for i in range(m, 0, -1):
	P1 = (P1 + get(a[i])) % K
	add(a[i], 1)
P = (P + P1) % K
print(P)


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')
T = Tp.TypeVar('T')

class FenwickSum(Tp.Generic[T]):
	__slots__ = ['nodes', 'size', 'unit']

	def __init__(self, size: int, default: T, unit: T):
		self.nodes = [default] * (size + 1)
		self.size = size + 1
		self.unit = unit

	def add(self, index: int, value: T):
		while index < self.size:
			self.nodes[index] += value
			index += index & -index

	def sum(self, right: int) -> T:
		result = self.unit
		while right:
			result += self.nodes[right]
			right -= right & -right
		return result

def main():
	n = int(input())
	a = list(map(int, input().split()))
	b = [x for x in a if x != -1]
	mod = 998244353
	minus = n - len(b)
	m_inv = pow(minus, mod - 2, mod)
	ans = 0
	bit = FenwickSum[int](n, 0, 0)
	for x in reversed(b):
		ans += bit.sum(x)
		bit.add(x, 1)
	ans += minus * (minus - 1) * pow(4, mod - 2, mod) % mod
	(acc_u, m) = ([0] * (n + 1), minus)
	for x in a:
		if x == -1:
			m -= 1
		else:
			acc_u[x] = m
	for i in range(n - 1, 0, -1):
		acc_u[i] += acc_u[i + 1]
		if acc_u[i] >= mod:
			acc_u[i] -= mod
	(acc_d, m) = ([0] * (n + 1), minus)
	for x in reversed(a):
		if x == -1:
			m -= 1
		else:
			acc_d[x] = m
	for i in range(1, n + 1):
		acc_d[i] += acc_d[i - 1]
		if acc_d[i] >= mod:
			acc_d[i] -= mod
	for x in set(range(1, n + 1)) - set(b):
		ans = (ans + (acc_u[x] + acc_d[x]) * m_inv) % mod
	print(ans % mod)
main()