G. Киберспорт в Берляндии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно киберспорт признали официальным спортом в Берляндии и начали проводить регулярные соревнования. На волне популярности Монокарп также решил поучаствовать в грядущих соревнованиях (к тому же призовые еще никому не помешали).

В каждый из следующих $$$n$$$ дней будет проводиться по одному соревнованию. Монокарп хотел бы поучаствовать во всех, но, к сожалению, его текущий уровень игры $$$s$$$ равен $$$0$$$. А от уровня игры зависит и размер призовых, на которые Монокарп может рассчитывать. Потому Монокарп решил, что может пожертвовать участием в некоторых соревнованиях, но зато он сможет в этот день потренироваться и повысить свой уровень игры.

В общем случае, в $$$i$$$-й день Монокарп может

  • либо принять участие в $$$i$$$-м соревновании и заработать $$$a_i + s$$$ призовых, где $$$s$$$ — это его текущий уровень игры;
  • либо пропустить соревнование, но потренироваться: Монокарп ничего не заработает, но увеличит свой уровень $$$s$$$ на $$$1$$$.

Помогите Монокарпу определить его максимально возможный суммарный доход. А также посчитайте количество планов тренировок, которые дадут такой доход.

Два плана тренировок считаются различными, если существует день, который в одном плане считается днем тренировки, а в другом — днем соревнования.

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

В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество дней, когда будут проходить соревнования.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — базовый размер призовых, на которые может рассчитывать Монокарп.

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

Выведите два целых числа — максимальный суммарный доход, который сможет получить Монокарп при оптимальном плане тренировок, и количество таких оптимальных планов.

Так как количество планов может быть очень большим, выведите это число по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
1
0
Выходные данные
0 2
Входные данные
1
42
Выходные данные
42 1
Входные данные
5
0 0 0 0 0
Выходные данные
6 2
Входные данные
6
5 4 3 2 1 0
Выходные данные
15 7
Входные данные
10
5 9 0 3 2 0 2 2 9 9
Выходные данные
53 3
Примечание

В первом примере Монокарп может как участвовать в соревновании, так и пропустить его — в обоих случаях он заработает $$$0$$$.

Во втором примере выгодно просто поучаствовать в единственном соревновании.

В третьем примере существует два плана тренировок. Монокарп может

  1. либо тренироваться первые два дня и участвовать в соревнованиях в остальные дни: Монокарп заработает $$$3 \cdot (0 + 2) = 6$$$ призовых;
  2. либо тренироваться первые три дня: тогда Монокарп также заработает $$$2 \cdot (0 + 3) = 6$$$ призовых.

В четвертом примере Монокарп может либо поучаствовать во всех соревнованиях, либо пропустить один любой день.