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.

题目背景

白王正在挑选容器。

题目描述

白王制造了 $n$ 个容器，并将它们排成了一队，从左到右依次编号为 $1 \sim n$。第 $i$ 个容器的强度为 $a_i$，保证 $a_i$ 互不相同。为了挑选出最纯粹的容器，白王会进行 $n-1$ 轮操作，每轮操作中，他会等概率随机挑选两个 位置相邻 且 未被击倒 的容器，令它们进行决斗，在一次决斗中，强度较小的容器将会被击倒并移出队列。

显然最后留下的是强度最大的容器，但是，可怜的容器们很想知道自己能够活多久，于是，它们请你对每个容器求出它存活轮数的期望。答案对 $998244353$ 取模。

一个容器的存活轮数为最大的非负整数 $x < n$ 满足它在第 $x$ 轮未被击倒。

两个容器 $i$ 和 $j$ 位置相邻当且仅当不存在 $k$ 满足 $i<k<j$ 且 $k$ 号容器未被击倒。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1, a_2,\cdots,a_n$，意义见题目描述。

输出格式

一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个容器的存活轮数的期望。为了避免浮点误差，保证答案可以表示为最简分数 $\frac{p}{q}$，你只需要输出一个 $x (0 \leq x < 998244353)$ 使得 $qx \equiv p \pmod {998244353}$。

3
3 1 2

2 0 1

3
1 2 3

499122177 499122177 2

5
1 4 2 3 5

499122178 249561091 665496236 582309207 4

提示

样例解释

在第一组样例中，第一个容器无论如何不可能被击倒，第二个容器在第一轮一定会被击倒，第三个容器第一轮一定不被击倒，第二轮一定被击倒。

第二组样例的真实答案为 $\frac{1}{2}$，$\frac{1}{2}$，$2$。

数据范围

对于所有测试点，保证 $1 \leq n \leq 50$，$1 \leq a_i \leq n$，$a_i$ 两两不同。

$\text{Subtask 1 (2 pts)}$ $n \leq 2$。

$\text{Subtask 2 (23 pts)}$ $n \leq 6$。

$\text{Subtask 3 (31 pts)}$ $n \leq 18$。

$\text{Subtask 4 (19 pts)}​$ $a_i = i$。

$\text{Subtask 5 (25 pts)}$ 无特殊限制。

提示

如果你不知道怎么对分数取模，可以参考这里。