努力不一定有奇迹，但不努力一定没有奇迹。

伞木希美有过迷茫，但没丧失前进的希望，尽管从南中到北宇治高中都不完美，尽管一直没机会参加全国大赛，但是却不曾放弃长笛，一直坚持着，不断的努力，不断的碰壁。即使没有凯冢霙（挚友）那般的才能，仍然坚持着。

但是命运就和她开了个天大的玩笑，事实不尽人意，哪怕拼劲全力，也总有人力所不能及的事情。但她仍爱着她的长笛，爱着她的生活。

【遗憾什么的，肯定没有】

题目

伞木希美即使是在退出北宇治高中吹奏部后依旧坚持练习长笛。每次练习结束她都会为自己的收获做一个记录。每隔 $n$ 天她都会进行一个回顾，来看看自己的成长曲线。

我们假设她每天的成长值为 $a_i$, 每次抽取一天或者多个不同的日期，找出选取天数的最大值。

问题

伞木希美拥有$2^n -1$ 种选取策略，找出不同种方式的最大值总和 。

输入

第一行 $n$($1 \leq n \leq 10^ 4$)

第二行 $a_1,a_2,......,a_n$($1 \leq a_i \leq 10^ 5$)

输出

不同种方式的最大值之和，对结果取模998244353

样例

3
4 2 7

38

样例解释

选择$a_1$ , 最大值为4；

选择$a_2$ , 最大值为2；

选择$a_3$ , 最大值为7；

选择$a_1，a_2$ , 最大值为4；

选择$a_1，a_3$ , 最大值为7；

选择$a_2， a_3$ , 最大值为7；

选择$a_1， a_2， a_3$ , 最大值为7。

所以答案为38。