D. Очередь с приоритетом
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана последовательность $$$A$$$, в которой каждый элемент записан в формате + x или -, где $$$x$$$ — целое число.

Для последовательности $$$S$$$, в которой каждый элемент записан в формате + x или -, определим $$$f(S)$$$ следующим образом:

  • Проходим по $$$S$$$ от первого элемента до последнего и поддерживаем мультимножество $$$T$$$, изначально пустое.
  • Если элемент последовательности имеет вид + x, добавим $$$x$$$ в $$$T$$$. Иначе удалим наименьший элемент из $$$T$$$ (если $$$T$$$ пусто, ничего делать не нужно).
  • После прохода по $$$S$$$ посчитаем сумму всех элементов в $$$T$$$. $$$f(S)$$$ полагается равным этой сумме.

Последовательность $$$b$$$ является подпоследовательностью последовательности $$$a$$$, если $$$b$$$ может быть получена из $$$a$$$ удалением нуля или больше элементов без изменения порядка оставшихся элементов. Для всех подпоследовательностей $$$B$$$ последовательности $$$A$$$ посчитайте сумму $$$f(B)$$$ по модулю $$$998\,244\,353$$$.

Входные данные

Первая строка содержит целое число $$$n$$$ ($$$1\leq n\leq 500$$$) – длину $$$A$$$.

Каждая из следующих $$$n$$$ строк начинается с символа операции + или -. Если символ равен +, то за ним следует целое число $$$x$$$ ($$$1\le x<998\,244\,353$$$). $$$i$$$-я строка из этих $$$n$$$ строк описывает $$$i$$$-й элемент $$$A$$$.

Выходные данные

Выведите одно целое число, равное ответу на задачу по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
4
-
+ 1
+ 2
-
Выходные данные
16
Входные данные
15
+ 2432543
-
+ 4567886
+ 65638788
-
+ 578943
-
-
+ 62356680
-
+ 711111
-
+ 998244352
-
-
Выходные данные
750759115
Примечание

В первом примере все возможные пары $$$B$$$ и $$$f(B)$$$ выглядят так:

  • $$$B=$$$ {}, $$$f(B)=0$$$.
  • $$$B=$$$ {-}, $$$f(B)=0$$$.
  • $$$B=$$$ {+ 1, -}, $$$f(B)=0$$$.
  • $$$B=$$$ {-, + 1, -}, $$$f(B)=0$$$.
  • $$$B=$$$ {+ 2, -}, $$$f(B)=0$$$.
  • $$$B=$$$ {-, + 2, -}, $$$f(B)=0$$$.
  • $$$B=$$$ {-}, $$$f(B)=0$$$.
  • $$$B=$$$ {-, -}, $$$f(B)=0$$$.
  • $$$B=$$$ {+ 1, + 2}, $$$f(B)=3$$$.
  • $$$B=$$$ {+ 1, + 2, -}, $$$f(B)=2$$$.
  • $$$B=$$$ {-, + 1, + 2}, $$$f(B)=3$$$.
  • $$$B=$$$ {-, + 1, + 2, -}, $$$f(B)=2$$$.
  • $$$B=$$$ {-, + 1}, $$$f(B)=1$$$.
  • $$$B=$$$ {+ 1}, $$$f(B)=1$$$.
  • $$$B=$$$ {-, + 2}, $$$f(B)=2$$$.
  • $$$B=$$$ {+ 2}, $$$f(B)=2$$$.

Сумма этих значений равна $$$16$$$.