D. 恶与饿
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
是啊……我现在可以做出自己的选择。

那么,我该相信谁。

该怎么选?

良的善恶在挣扎。

良的原则可以抽象为有 $$$n$$$ 个部分,每一部分权重为 $$$a_i$$$。

良的善念与这个长度为 $$$n$$$ 的序列所有的上升子序列的和有关。

现在请你计算这个值。

形式化的:给定一个长度为 $$$n$$$ 的序列 $$$a_1, a_2, \cdots, a_n$$$,现在请你计算下列计算式的值。 $$$$$$ W = \sum_{S\subseteq N}\sum_{i=1}^{|S|}a_{S_i} $$$$$$ 其中 $$$N$$$ 为 $$$\{1,2,\cdots,n\}$$$,$$$S$$$ 为 $$$N$$$ 的子集,且满足 $$$\forall i \in [2, |S|]$$$ 都有 $$$a_{S_{i - 1}} \lt a_{S_i}$$$。

现在你需要计算 $$$W$$$ 的值,由于答案可能非常大,请输出对 $$$998244353$$$ 取模后的答案。

Input

第一行输入一个正整数 $$$n$$$($$$1\le n \le 5\times 10^5$$$),表示序列长度。

第二行输入 $$$n$$$ 个正整数 $$$a_1,a_2,\cdots,a_n$$$($$$1\le a_i\le 10^9$$$),描述了序列。

Output

输出一个整数,表示答案。

Example
Input
3
5 2 3
Output
15