You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

T2 差后队列（queue）

题目描述

定义差后队列为一个数据结构，支持两种操作：

• pop 随机删除一个不是最大值的的数。如果只有一个数则删除该数。
• push 插入一个数（正常插入）。

给定操作序列，求每次删的数的期望，以及每个数期望被删的时间（如果到最后也没被删则删除时间为 $0$）。

输入格式

第一行一个整数 $n$ 表示操作数。

接下来 $n$ 行，每行一个操作。0 x 表示 push，1 表示 pop。

输出格式

一行输出 $n$ 个整数，如果是 $0$ 操作就输出该数被删除时间（指在哪一步操作被删除）的期望，否则输出该操作删除的数的期望大小。答案对 $998244353$ 取模。

样例1

样例输入

10
0 300036489
0 49528961
1
0 450735376
0 8021539
1
1
1
0 727178284
1

样例输出

499122183 3 49528961 8 499122183 154029014 154029014 450735376 10 727178284

数据范围

$\texttt{Subtask1(50pts)}:n,m\leq 5000$。

$\texttt{Subtask2(50pts)}:$ 无特殊限制。

对于 $100\%$ 的数据满足 $n\leq 10^6$，$0<x<998244353$，$x$ 互不相同。