CF1876D Lexichromatography

Pak Chanek 非常热爱他所在的学院——印度尼西亚大学计算机科学学院（Fasilkom）。他想用学院标志的两种颜色——蓝色和红色——来玩一个数组染色的游戏。 给定一个包含 $n$ 个元素的数组 $a$，第 $i$ 个元素的值为 $a_i$。Pak Chanek 想要将数组中的每个元素染成蓝色或红色，使得满足以下条件： - 如果将所有蓝色元素按原顺序组成一个子序列，所有红色元素也按原顺序组成一个子序列，则蓝色子序列在字典序上严格小于红色子序列。 - 数组 $a$ 不存在任何不平衡的子数组。一个子数组被称为不平衡，当且仅当存在某个值 $k$，使得该子数组中值为 $k$ 的蓝色元素个数与红色元素个数的绝对差值大于等于 $2$。 - 注意，允许将数组的所有元素染成同一种颜色。 有多少种不同的染色方案满足上述所有条件？由于答案可能非常大，请输出答案对 $998\,244\,353$ 取模后的结果。若存在至少一个元素在一种染色方案中为蓝色，在另一种染色方案中为红色，则这两种染色方案视为不同。 $^\dagger$ 一个数组的子序列是指可以通过删除一些元素（可能不删），且不改变剩余元素顺序得到的序列。 $^\ddagger$ 设 $p$ 和 $q$ 是两个不同的序列。若 $p$ 是 $q$ 的前缀，或存在某个下标 $i$，使得对于所有 $1\leq j

第一行包含一个整数 $n$（$1 \leq n \leq 2\cdot10^5$），表示数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1,a_2,a_3,\ldots,a_n$（$1\leq a_i\leq2\cdot10^5$）。

输出一个整数，表示满足所有条件的不同染色方案数，对 $998\,244\,353$ 取模。

在第一个样例中，从第 $1$ 个到第 $8$ 个元素的染色有 $3$ 种方案： - 蓝、红、红、蓝、蓝、红、红、蓝。 - 蓝、红、红、红、蓝、蓝、红、蓝。 - 红、红、蓝、蓝、蓝、红、红、蓝。 例如，如果将第 $1$ 到第 $8$ 个元素染成红、红、蓝、红、红、蓝、蓝、蓝，这不是一个合法的染色方案，因为对于子数组 $a[2..6]$，值为 $3$ 的蓝色元素有 $0$ 个，红色元素有 $2$ 个，使得该子数组是不平衡的。 由 ChatGPT 4.1 翻译