← 返回题目列表

AtCoder · arc160_c

C. 通电

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给你一个正整数的多重集 N 元素: A=\lbrace A_1,A_2,\dots,A_N \rbrace.

您可以重复以下操作任意次数(可能为零)。

  • 选择一个正整数 x 至少出现两次 A。删除两次出现的 x 来自 A,并添加出现一次 x+1 to A.

求模数 998244353,多重集 A 可以到底。

约束

  • 1 \le N \le 2 \times 10^5
  • 1 \le A_i \le 2 \times 10^5

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N

输出

打印答案。


示例输入 1

4
1 1 2 4

示例输出 1

3

A 可以是三个多重集之一 \lbrace 1,1,2,4 \rbrace,\lbrace 2,2,4 \rbrace,\lbrace 3,4 \rbrace 最后。

你可以 A = \lbrace 3,4 \rbrace 如下。

  • 选择 x = 1。删除两个 1来自 A 并添加一个 2 to A, 制作 A=\lbrace 2,2,4 \rbrace.
  • 选择 x = 2。删除两个 2来自 A 并添加一个 3 to A, 制作 A=\lbrace 3,4 \rbrace.

示例输入 2

5
1 2 3 4 5

示例输出 2

1

示例输入 3

13
3 1 4 1 5 9 2 6 5 3 5 8 9

示例输出 3

66