Number of Increasing Subsequences

Interview

Time limit2sMemory limit1024 MB

Summary

For each position i, count the increasing subsequences that end at A_i, modulo 998244353, where values range up to 5000.

Problem

You are given a sequence $A$ of length $N$ . For each $i$ , find the number of increasing subsequences that end with $A_i$ .

The answer can be very large, so output it modulo $998\,244\,353$ .

For those who are not sure what an increasing subsequence is, Dongwon has prepared the following definitions.

A subsequence is a sequence obtained by choosing one or more elements from the given sequence and listing them in their original order.
An increasing subsequence is a sequence in which every element except the first is greater than the element immediately before it. That is, for a subsequence $A$ of length $N$ , if $A_{i-1} < A_i$ holds for all $2 \le i \le N$ , then $A$ is an increasing subsequence.

Dongwon adds a note that, by this definition, a subsequence of length 1 is always an increasing subsequence.

The first line gives the length of the sequence, $N$ .

The second line gives $N$ integers $A_1, A_2, \cdots, A_N$ separated by spaces.

Print $N$ integers on the first line.

The $i$ -th number printed is the number of increasing subsequences ending with $A_i$ , modulo $998\,244\,353$ .