CF1542D.Priority Queue

You are given a sequence $A$, where its elements are either in the form + x or -, where $x$ is an integer.

For such a sequence $S$ where its elements are either in the form + x or -, define $f(S)$ as follows:

• iterate through $S$'s elements from the first one to the last one, and maintain a multiset $T$ as you iterate through it.
• for each element, if it's in the form + x, add $x$ to $T$; otherwise, erase the smallest element from $T$ (if $T$ is empty, do nothing).
• after iterating through all $S$'s elements, compute the sum of all elements in $T$. $f(S)$ is defined as the sum.

The sequence $b$ is a subsequence of the sequence $a$ if $b$ can be derived from $a$ by removing zero or more elements without changing the order of the remaining elements. For all $A$'s subsequences $B$, compute the sum of $f(B)$, modulo $998\,244\,353$.

给你一个序列 $A$，其中每个元素的形式为 \+ x 或 -，其中 $x$ 是一个整数。

对于一个序列 $S$（其每个元素的形式同样为 \+ x 或 -），定义函数 $f(S)$ 如下：

• 从第一个元素开始，依次遍历 $S$ 的所有元素，并在遍历过程中维护一个多重集合 $T$；
• 对于每个元素：
  • 若其形式为 \+ x，则将 $x$ 加入 $T$；
  • 若其形式为 -，则从 $T$ 中删除最小的元素（若 $T$ 为空，则不执行任何操作）；
• 遍历完 $S$ 的所有元素后，计算 $T$ 中所有元素的和；该和即为 $f(S)$ 的值。

若序列 $b$ 可通过从序列 $a$ 中删除零个或多个元素（不改变剩余元素的相对顺序）得到，则称 $b$ 是 $a$ 的一个子序列。
对 $A$ 的所有子序列 $B$，求 $\sum f(B)$ 的值，并对 $998\,244\,353$ 取模。

The first line contains an integer $n$ ($1\leq n\leq 500$) — the length of $A$.

Each of the next $n$ lines begins with an operator + or -. If the operator is +, then it's followed by an integer $x$ ($1\le x \lt 998\,244\,353$). The $i$-th line of those $n$ lines describes the $i$-th element in $A$.

第一行包含一个整数 $n$（$1\leq n\leq 500$）—— 表示数组 $A$ 的长度。

接下来的 $n$ 行，每行以操作符 + 或 - 开头。若操作符为 +，则其后跟随一个整数 $x$（$1\le x \lt 998\,244\,353$）。这 $n$ 行中的第 $i$ 行描述了数组 $A$ 的第 $i$ 个元素。

Print one integer, which is the answer to the problem, modulo $998\,244\,353$.

输出一个整数，即该问题的答案对 $998\,244\,353$ 取模的结果。

In the first example, the following are all possible pairs of $B$ and $f(B)$:

• $B=$ {}, $f(B)=0$.
• $B=$ {-}, $f(B)=0$.
• $B=$ {+ 1, -}, $f(B)=0$.
• $B=$ {-, + 1, -}, $f(B)=0$.
• $B=$ {+ 2, -}, $f(B)=0$.
• $B=$ {-, + 2, -}, $f(B)=0$.
• $B=$ {-}, $f(B)=0$.
• $B=$ {-, -}, $f(B)=0$.
• $B=$ {+ 1, + 2}, $f(B)=3$.
• $B=$ {+ 1, + 2, -}, $f(B)=2$.
• $B=$ {-, + 1, + 2}, $f(B)=3$.
• $B=$ {-, + 1, + 2, -}, $f(B)=2$.
• $B=$ {-, + 1}, $f(B)=1$.
• $B=$ {+ 1}, $f(B)=1$.
• $B=$ {-, + 2}, $f(B)=2$.
• $B=$ {+ 2}, $f(B)=2$.

The sum of these values is $16$.

在第一个例子中，以下是所有可能的 $B$ 与 $f(B)$ 的组合：

• $B=$ {}，$f(B)=0$。
• $B=$ {-}，$f(B)=0$。
• $B=$ {+ 1, -}，$f(B)=0$。
• $B=$ {-, + 1, -}，$f(B)=0$。
• $B=$ {+ 2, -}，$f(B)=0$。
• $B=$ {-, + 2, -}，$f(B)=0$。
• $B=$ {-}，$f(B)=0$。
• $B=$ {-, -}，$f(B)=0$。
• $B=$ {+ 1, + 2}，$f(B)=3$。
• $B=$ {+ 1, + 2, -}，$f(B)=2$。
• $B=$ {-, + 1, + 2}，$f(B)=3$。
• $B=$ {-, + 1, + 2, -}，$f(B)=2$。
• $B=$ {-, + 1}，$f(B)=1$。
• $B=$ {+ 1}，$f(B)=1$。
• $B=$ {-, + 2}，$f(B)=2$。
• $B=$ {+ 2}，$f(B)=2$。

这些值的总和为 $16$。