题目描述

clay17 是一位热爱奶茶的品鉴达人。

她为她最喜欢的奶茶编号，编号为大于等于1的正整数。

给定一个奶茶序列a，表示她在某一天品鉴的奶茶顺序。然而，clay17 不希望奶茶之间发生“串味”——即不同奶茶的风味混合在一起。为了量化这种“串味”的程度，我们定义了一个指标。 对于序列中任意一段连续的奶茶子序列（从第 l 杯到第 r 杯），我们定义其“串味程度”f(l,r)为这段子序列中所有奶茶编号构成的集合的子集数量。 - 注意，集合中的元素是互不相同的，而原序列中可能存在重复的奶茶编号。

clay17 希望计算这一天所有可能的子序列的“串味程度”之和，记为 sum。具体计算方式如下：

for(int l=1;l<=n;l++){
    for(int r=l;r<=n;r++){
        sum = sum + f(l,r);
        sum %= 998244353;
    }
}

由于clay17不太聪明，她对安排奶茶的顺序并不擅长，也不感兴趣。她只希望你能帮她算出来这个sum，并对998244353取模。

输入格式

• 第一行,一个正整数n，表示序列a的长度
• 第二行,n个正整数，表示奶茶序列

输出格式

共一行，一个整数，表示sum对998244353取模的结果。

示例

input

5
1 2 3 4 5

output

114

数据范围

• 对于 20% 的数据点，满足 1 ≤ n ≤ 500 且 a[i] ≤ 1e5
• 对于 40% 的数据点，满足 1 ≤ n ≤ 5000 且 a[i] ≤ 1e5
• 对于 60% 的数据点，满足 1 ≤ n ≤ 5000 且 a[i] ≤ 1e9
• 对于所有的数据点，保证 1 ≤ n ≤ 1000000 且 a[i] ≤ 1e9

限制

• 每个测试的时间限制：1s

• 每个测试的内存限制：512 MB

出题人的碎碎念

• 良心出题人不卡常
• 良心出题人在题干中已经展示了核心代码(doge)
• 想不出来正解的话，可以看看题目名~