D. 执行操作后的最大MEX

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

给你一个下标从 0 开始的整数数组 a 和一个整数 v 。

在一步操作中,你可以对 a 中的任一元素加上或减去 v 。

  • 例如,如果 a = [1,2,3] 且 v = 2 ,你可以选择 a[0] 减去 v ,得到 a = [-1,2,3] 。

数组的 MEX 是指数组中缺失的最小非负整数。

  • 例如,[-1,2,3] 的 MEX 是 0 ,而 [1,0,3] 的 MEX 是 2 。

返回在执行上述操作 任意次 后,a 的最大 MEX 。

输入格式

第一行:n

第二行:n个整数

第三行:v

输出格式

a 的最大 MEX

样例

示例 1:

输入:

6
1 -10 7 13 6 8
5

输出:

4

解释:数组为[1,-10,7,13,6,8],v=5,多次操作变为正数并取余之后为[1,0,2,3,1,3]。0~3不缺失,当取4时缺失,所以最终返回为4。

示例 2:

输入:

6
1 -10 7 13 6 8
7

输出:

2

解释:数组为[1,-10,7,13,6,8],v=7,多次操作变为正数并取余之后为[1,4,0,6,6,1]。0~1不缺失,当取2时缺失,所以最终返回为2。

示例 3:

输入:

13
3 2 3 1 0 1 4 2 3 1 4 1 3
5

输出:

5

解释:数组为[3,2,3,1,0,1,4,2,3,1,4,1,3],v=5,无需操作。0~4不缺失,当等于5时再取0缺失,所以最终返回为5。

示例 4:

输入:

10
3 0 3 2 4 2 1 1 0 4
5

输出:

10

解释:数组为[3,0,3,2,4,2,1,1,0,4],v=5,无需操作。0~4不缺失,5~9时再次取0~4也不缺失,所以最终返回为10。

数据范围与提示

1 <= n, v <= 10^5

-109 <= a[i] <= 10^9