暂无测试数据。

题目描述

Daniel 正在玩一个战棋游戏。
现在 Daniel 有 \(n\) 队士兵站在 \(x\) 轴上。
第 \(i\) 队士兵有 \(a_i\) 人，坐标为 \(x_i\)。

Daniel 看到一队士兵有这么多人，
都站在同一个位置，他对此很不满意。
他想命令一些士兵移动到新的位置（必须是整点），使得不存在两个士兵站在同一个位置。
为了节约时间，Daniel 希望每个士兵的移动距离的最大值尽可能小。
请求出这个最小值。

输入

第一行，一个正整数 \(n\)，表示 Daniel 有多少队士兵。
第二行，\(n\) 个正整数 \(ai\)，表示每队士兵的人数。
第三行，\(n\) 个严格递增的整数 \(xi\)，表示每队士兵的坐标。

输出

一行一个非负整数，表示每个士兵的移动距离的最大值的最小值。

样例输入

2
2 3
0 2

样例输出

1

提示

移动后，5 个士兵的坐标分别为 1,0,1, 2, 3。
有 2 个士兵移动距离为 0，
3 个士兵移动距离为 1，因此答案是 1。

数据范围限制

\(1 \leq n \leq 10^5\)，坐标在 int 范围内。

来源

基础篇补充6.8