CF1876D.Lexichromatography

Pak Chanek loves his faculty, the Faculty of Computer Science, University of Indonesia (Fasilkom). He wants to play with the colours of the faculty's logo, blue and red.

There is an array $a$ consisting of $n$ elements, element $i$ has a value of $a_i$. Pak Chanek wants to colour each element in the array blue or red such that these following conditions are satisfied:

• If all blue elements are formed into a subsequence$^\dagger$ and so are all the red elements, the blue subsequence is strictly less than the red subsequence lexicographically$^\ddagger$.
• Array $a$ does not have any subarray that is imbalanced. A subarray is imbalanced if and only if there is a value $k$ such that the absolute difference between the number of blue elements with value $k$ and the number of red elements with value $k$ in this subarray is $2$ or more.
• Note that it is possible to colour every element of the array the same colour.

How many different colourings satisfy all those conditions? Since the answer can be very big, print the answer modulo $998\,244\,353$. Two colourings are different if and only if there is at least one element that is blue in one colouring, but red in the other.

$^\dagger$ A subsequence of an array is a sequence that can be obtained from the array by deleting some elements (possibly none), without changing the order of the remaining elements.

$^\ddagger$ Let $p$ and $q$ be two different sequences. Sequence $p$ is said to be lexicographically less than sequence $q$ if and only if $p$ is a prefix of $q$ or there is an index $i$ such that $p_j=q_j$ holds for every $1\leq j \lt i$, and $p_i \lt q_i$. In particular, an empty sequence is always lexicographically less than any non-empty sequence.

帕克·查内克热爱他的学院——印度尼西亚大学计算机科学学院（Fasilkom）。他想玩转学院标志的两种颜色：蓝色与红色。

给定一个由 $n$ 个元素组成的数组 $a$，其中第 $i$ 个元素的值为 $a_i$。帕克·查内克希望将数组中每个元素染成蓝色或红色，使得以下条件全部满足：

• 若将所有蓝色元素按其在原数组中的相对顺序提取出来构成一个子序列$^\dagger$，红色元素同理也构成一个子序列，则蓝色子序列在字典序上严格小于红色子序列$^\ddagger$。
• 数组 $a$ 的任意子数组均不能是“不平衡的”。一个子数组被称为不平衡的，当且仅当存在某个值 $k$，使得该子数组中值为 $k$ 的蓝色元素个数与值为 $k$ 的红色元素个数之差的绝对值大于等于 $2$。
• 注意：允许将数组中所有元素染成同一种颜色。

有多少种不同的染色方案满足上述所有条件？由于答案可能非常大，请输出答案对 $998\,244\,353$ 取模的结果。两种染色方案不同，当且仅当存在至少一个元素，在一种方案中被染为蓝色，而在另一种方案中被染为红色。

$^\dagger$ 数组的一个子序列是指通过删除原数组中若干（可能为零）个元素（不改变剩余元素的相对顺序）所得到的序列。

$^\ddagger$ 设 $p$ 和 $q$ 是两个不同的序列。称序列 $p$ 在字典序上严格小于序列 $q$，当且仅当 $p$ 是 $q$ 的前缀，或者存在某个下标 $i$，使得对所有 $1 \leq j < i$ 均有 $p_j = q_j$，且 $p_i < q_i$。特别地，空序列在字典序上恒小于任何非空序列。

The first line contains a single integer $n$ ($1 \leq n \leq 2\cdot10^5$) — the size of array $a$.

The second line contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ ($1\leq a_i\leq2\cdot10^5$).

第一行包含一个整数 $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$）。

An integer representing the number of different colourings that satisfy all of the problem's conditions, modulo $998\,244\,353$.

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

In the first example, the $3$ ways for colouring all elements from index $1$ to index $8$ are:

• Blue, red, red, blue, blue, red, red, blue.
• Blue, red, red, red, blue, blue, red, blue.
• Red, red, blue, blue, blue, red, red, blue.

As an example, if we colour the elements from index $1$ to index $8$ to be red, red, blue, red, red, blue, blue, blue, it is not valid colouring, because for subarray $a[2..6]$, there are $0$ blue elements with value $3$ and $2$ red elements with value $3$, making subarray $a[2..6]$ an imbalanced subarray.

在第一个例子中，对索引 $1$ 到索引 $8$ 的所有元素进行染色的 $3$ 种方式为：

• 蓝、红、红、蓝、蓝、红、红、蓝。
• 蓝、红、红、红、蓝、蓝、红、蓝。
• 红、红、蓝、蓝、蓝、红、红、蓝。

例如，若将索引 $1$ 到索引 $8$ 的元素染成红、红、蓝、红、红、蓝、蓝、蓝，则该染色方案不合法，因为对于子数组 $a[2..6]$，其蓝色元素个数为 $0$（对应值为 $3$），红色元素个数为 $2$（对应值为 $3$），导致子数组 $a[2..6]$ 成为一个不平衡子数组。