310950: CF1912K. Kim's Quest

K. Kim's Questtime limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

In the long-forgotten halls of Kombinatoria's ancient academy, a gifted mathematician named Kim is faced with an unusual challenge. They found an old sequence of integers, which is believed to be a cryptic message from the legendary Kombinatoria's Oracle, and Kim wants to decipher its hidden meaning.

Kim's mission is to find specific patterns within the sequence, known as Harmonious Subsequences. These are extraordinary subsequences where the sum of every three consecutive numbers is even, and each subsequence must be at least three numbers in length.

Given a sequence $a_i$ ($1 \le i \le n$) of length $n$, its subsequence of length $m$ is equal to $a_{b_1}, a_{b_2}, \ldots, a_{b_m}$ and is uniquely defined by a set of $m$ indices $b_j$, such that $1 \le b_1 < b_2 < \ldots < b_m \le n$. Subsequences given by different sets of indices $b_j$ are considered different.

There's a twist in Kim's quest: the number of these Harmonious Subsequences could be overwhelming. To report the findings effectively, Kim must calculate the total number of these subsequences, presenting the answer as a remainder after dividing by the number $998\,244\,353$.

Input

The first line contains a single integer $n$ — the length of the sequence ($3 \le n \le 2 \cdot 10^5$).

The second line contains $n$ space-separated integers $a_i$ — the elements of the sequence ($1 \le a_i \le 2 \cdot 10^5$).

Output

Output one number — the number of Harmonious Subsequences, modulo $998\,244\,353$.

ExamplesInput

3
1 2 3

Output

1

Input

5
2 8 2 6 4

Output

16

Input

5
5 7 1 3 5

Output

0

Input

11
3 1 4 1 5 9 2 6 5 3 6

Output

386

Input

54
2 1 1 1 1 2 1 2 2 2 2 1 1 1 2 1 1 2
2 1 2 2 2 2 2 2 2 1 1 1 2 2 1 1 1 1
2 2 1 1 2 2 2 2 2 1 1 1 2 2 1 2 1 1

Output

0

Note

In the provided input data for the fifth sample, the sequence of numbers is split into three separate lines for clarity, but it should be understood that in the actual test data, the sequence is given in one line. The actual number of Harmonious Subsequences in this example is $4\,991\,221\,765 = 5 \times 998\,244\,353$, hence the output is zero as a result of finding its remainder after dividing by the number $998\,244\,353$.

题目大意：
在Kombinatoria古老学院的长久被遗忘的厅堂中，一位名叫Kim的天才数学家面临着一个不同寻常的挑战。他们发现了一个古老的整数序列，这个序列被认为是来自传奇的Kombinatoria神谕的加密信息，Kim想要解码其隐藏的含义。Kim的任务是在这个序列中找到特定的模式，称为“和谐子序列”。这些子序列非常特殊，因为每三个连续数字的和是偶数，且每个子序列必须至少有三个数字。

给定一个长度为n的序列a_i（1 ≤ i ≤ n），它的长度为m的子序列等于a_{b_1}, a_{b_2}, …, a_{b_m}，并且由一个包含m个指数b_j的集合唯一确定，满足1 ≤ b_1 < b_2 < … < b_m ≤ n。由不同指数集合b_j给出的子序列被认为是不同的。

Kim的任务中有一个转折：这些和谐子序列的数量可能非常多。为了有效地报告这些发现，Kim必须计算这些子序列的总数，并以998,244,353取余后的结果呈现答案。

输入输出数据格式：
输入：
- 第一行包含一个整数n——序列的长度（3 ≤ n ≤ 2 * 10^5）。
- 第二行包含n个空格分隔的整数a_i——序列的元素（1 ≤ a_i ≤ 2 * 10^5）。

输出：
- 输出一个数——和谐子序列的数量，模998,244,353。

示例：
```
输入：
3
1 2 3
输出：
1

输入：
5
2 8 2 6 4
输出：
16

输入：
5
5 7 1 3 5
输出：
0

输入：
11
3 1 4 1 5 9 2 6 5 3 6
输出：
386

输入：
54
2 1 1 1 1 2 1 2 2 2 2 1 1 1 2 1 1 2
2 1 2 2 2 2 2 2 2 1 1 1 2 2 1 1 1 1
2 2 1 1 2 2 2 2 2 1 1 1 2 2 1 2 1 1
输出：
0
```
注意：在第五个示例的提供的输入数据中，数字序列为了清晰起见被分成三行，但在实际的测试数据中，序列是在一行中给出的。这个示例中的和谐子序列的实际数量是4,991,221,765 = 5 × 998,244,353，因此输出是0，这是在除以998,244,353后得到的余数。题目大意： 在Kombinatoria古老学院的长久被遗忘的厅堂中，一位名叫Kim的天才数学家面临着一个不同寻常的挑战。他们发现了一个古老的整数序列，这个序列被认为是来自传奇的Kombinatoria神谕的加密信息，Kim想要解码其隐藏的含义。Kim的任务是在这个序列中找到特定的模式，称为“和谐子序列”。这些子序列非常特殊，因为每三个连续数字的和是偶数，且每个子序列必须至少有三个数字。 给定一个长度为n的序列a_i（1 ≤ i ≤ n），它的长度为m的子序列等于a_{b_1}, a_{b_2}, …, a_{b_m}，并且由一个包含m个指数b_j的集合唯一确定，满足1 ≤ b_1 < b_2 < … < b_m ≤ n。由不同指数集合b_j给出的子序列被认为是不同的。 Kim的任务中有一个转折：这些和谐子序列的数量可能非常多。为了有效地报告这些发现，Kim必须计算这些子序列的总数，并以998,244,353取余后的结果呈现答案。 输入输出数据格式： 输入： - 第一行包含一个整数n——序列的长度（3 ≤ n ≤ 2 * 10^5）。 - 第二行包含n个空格分隔的整数a_i——序列的元素（1 ≤ a_i ≤ 2 * 10^5）。 输出： - 输出一个数——和谐子序列的数量，模998,244,353。 示例： ``` 输入： 3 1 2 3 输出： 1 输入： 5 2 8 2 6 4 输出： 16 输入： 5 5 7 1 3 5 输出： 0 输入： 11 3 1 4 1 5 9 2 6 5 3 6 输出： 386 输入： 54 2 1 1 1 1 2 1 2 2 2 2 1 1 1 2 1 1 2 2 1 2 2 2 2 2 2 2 1 1 1 2 2 1 1 1 1 2 2 1 1 2 2 2 2 2 1 1 1 2 2 1 2 1 1 输出： 0 ``` 注意：在第五个示例的提供的输入数据中，数字序列为了清晰起见被分成三行，但在实际的测试数据中，序列是在一行中给出的。这个示例中的和谐子序列的实际数量是4,991,221,765 = 5 × 998,244,353，因此输出是0，这是在除以998,244,353后得到的余数。