human
Give me a Python code to print a single integer — the expected total number of inversions in the resulting valid permutation given the following:
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 P/Q where P and Q are non-negative integers and Q ≠ 0. Report the value of P ⋅ Q^{-1} \pmod {998244353}.

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of the sequence.

The second line contains n integers p_1, p_2, ..., p_n (-1 ≤ p_i ≤ n, p_i ≠ 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 P/Q where P and Q are non-negative integers and Q ≠ 0. Report the value of P ⋅ 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 (2 ⋅ 1 + 3 ⋅ 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.
assistant
#Here is Python code to print a single integer — the expected total number of inversions in the resulting valid permutation.

#!/usr/bin/env python
"""
This file is part of https://github.com/Cheran-Senthil/PyRival.

Copyright 2018 Cheran Senthilkumar all rights reserved,
Cheran Senthilkumar <hello@cheran.io>
Permission to use, modify, and distribute this software is given under the
terms of the MIT License.

"""
from __future__ import division, print_function

# import cmath
import itertools
# import math
import operator as op
# import random
import sys
from atexit import register
# from bisect import bisect_left, bisect_right
# from collections import Counter, MutableSequence, defaultdict, deque
# from copy import deepcopy
# from decimal import Decimal
# from difflib import SequenceMatcher
# from fractions import Fraction
# from heapq import heappop, heappush

if sys.version_info[0] < 3:
    # from cPickle import dumps
    from io import BytesIO as stream
    # from Queue import PriorityQueue, Queue
else:
    # from functools import reduce
    from io import StringIO as stream
    # from pickle import dumps
    # from queue import PriorityQueue, Queue

if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip

def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda:...