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: interview

Starter code:

Solutions:
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) 



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
        #D[i] is the position of i in the list
        #T[D[i]] is how many -1s there are to the left of it
        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)


import sys
input = sys.stdin.readline

n=int(input())
P=list(map(int,input().split()))
mod=998244353

INV=[None]*(n+1)#1/aのリストを予め作っておく.
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


#print(ANS,LEFT,AVEP)
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

#print(BLALIST)
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

#print(ANS)

A=NONBLA

if A==[]:
    print(ANS)
    return


n=len(A)
MAXA=max(A)
MINA=min(A)


BIT=[0]*(MAXA-MINA+2)#出現回数をbit indexed treeの形でもっておく.

for i in range(n):#A[0],A[1],...とBITを更新
    bitobje=A[i]-MINA+1

    x=bitobje
    while x!=0:
        ANS=(ANS-BIT[x])%mod
        x-=(x&(-x))

    #print(ANS)

    x2=MAXA-MINA+1
    #print(x2)
    while x2!=0:
        #print(x2,BIT)
        ANS=(ANS+BIT[x2])%mod
        x2-=(x2&(-x2))

    #print(ANS)

    y=bitobje
    while y<=MAXA-MINA+1:
        BIT[y]+=1
        y+=(y&(-y))

    #print(ANS,BIT)

print(ANS)



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)



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)

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)