問題一覧 > 通常問題

No.2815 Smaller than all

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 21
作問者 : Magentor / テスター : hirayuu_yc highlighter keisuke6 Yoyoyo8128 fact493 zeta7532 warabi0906
お気に入りにしたユーザー ProblemId : 11001 / 自分の提出
問題文最終更新日: 2024-07-19 22:02:07
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 437 ('09 Contest 002 day2) (順位表) の他の問題:

Problem Statement

You are given a sequence of positive integers $A=(A_1,A_2,\dots,A_N)$ of length $N$. Consider the following problem.

You are given an integer sequence a sequence of positive integers (corrected at 21:53) $S$. Find the lexicographically largest sequence of positive integers $T$ of length $N$ that satisfies the following condition. It can be shown that the lexicographically largest $T$ always exists. (added at 22:00)
  • Every (not necessarily contiguous) subsequence of length $|S|$ of the sequence of positive integers $T$ is lexicographically less than or equal to $S$.

Find the number, modulo $998244353$, of sequences of positive integers $S$ of length at least $1$ and at most $N$ such that the answer to the problem above is equal to $A=(A_1,A_2,\dots,A_N)$.

Here, a subsequence of an integer sequence is an integer sequence obtained by deleting $0$ or more elements from it and arranging the remaining elements without changing their order.

What is the lexicographical order on sequences?

$A=(A_1,A_2,\dots,A_{|A|})$ is lexicographically less than or equal to $B=(B_1,B_2,\dots,B_{|B|})$ if one of the following $2$ conditions holds. Here, $|A|,|B|$ denote the lengths of $A,B$, respectively.

  • $|A| \leq |B|$ and $(A_1,A_2,\dots,A_{|A|})=(B_1,B_2,\dots,B_{|A|})$.
  • There exists an integer $1 \leq i \leq \min(|A|,|B|)$ such that both of the following $2$ statements hold.
    • $(A_1,A_2,\dots,A_{i-1})=(B_1,B_2,\dots,B_{i-1})$
    • $A_i<B_i$

Constraints

  • All input values are integers.
  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i \leq10^9$

Input

The input is given from Standard Input in the following format.

$N$
$A_1\ A_2\ \dots\ A_N$

Output

Print the answer in $1$ line.

Sample

Sample 1
Input
3
1 1 2
Output
2

It can be proved that only $S=(1,1,2),(1,2)$ satisfy the condition. For example, when $S=(1,2)$, the possible subsequences of $(1,1,2)$ are $(1,1),(1,2),(1,2)$, all of which are lexicographically less than or equal to $(1,2)$. It can also be verified that $(1,1,2)$ is the lexicographically largest in this case, so $(1,2)$ satisfies the condition.

Sample 2
Input
5
1 1 1 1 1
Output
5

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。