思路总览

给定是一个 $1\sim n$ 的排列。设全局最长上升子序列（LIS）长度为 $L$。 对每个位置 $i$，我们只需统计：有多少条 LIS 会“经过”元素 $a_i$。

经典分解法：

• 令 Lend[i]：以位置 i 结尾的最长上升子序列长度；
• 令 CntL[i]：达到 Lend[i] 的方案数；
• 令 Rbeg[i]：从位置 i 开始（包含 i）的最长上升子序列长度（向右）；

题目内容

给定一个长为$n$ 的排列 {$a$}。排列是指，{$a$} 包含$1$~$n$中的所有元素恰好一次。

回顾一下，{$a$} 的一个子序列是指从{$a$}中将若干元素(不一定连续)提取出来而不改变相对位置形成 的序列。 对于 {$a$} 的一个子序列 {$b$}，如果 {$b$} 中的元素单调递增，就称{$b$}是{$a$}的一个上升子序列。 对于{$a$}的一个上升子序列{$c$}，如果找不到比{$c$}元素个数更多的上升子序列了，就称 {$c$} 是 {$a$} 的 一个最长上升子序列。显然，{$a$} 可以有很多个最长上升子序列。 请你对每个$i∈[1,n]$，求出有多少个不同的{$a$}的最长上升子序列包含$a_i$。

输入描述

第一行一个正整数$n$

第二行n个正整数，以空格分隔，表示$a_1,a_2,...,a_n$

保证 {$a$} 是一个 $1$~$n$ 的排列。 $1≤n≤2×10^5$

输出描述

输出 $n$ 行，每一行一个非负整数。第i行的输出表示包含$a$ 的最长上升子序列个数。

因为答案可能很大，所以你只需要输出答案对$998244353$取模的结果。

样例1

输入

5
3 1 4 2 5

输出

1
2
2
1
3

说明

对于输入的排列，其最长上升子序列长度为$3$，所有不同的最长上升了序列如下:

• $1,2,5$。
• $1, 4, 5$。
• $3, 4,5$。

以 $a_1$和 $a_2$为例。 包含了$a_1=3$的最长上升子序列有$1$个，故答案为$1$。 包含了$a_2=1$的最长上升子序列有$2$ 个，故答案为$2$。