2090: 排队形

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:0

题目描述

学校从各个班级中抽出不同人数的学生来组成一个学校的啦啦操队伍。初始的时候每个班级有 ai 个人,呈纵队排列,坐标为 xi ,由于每个班级的学生都是纵队排列,所以每个班级所有学生的位置坐标都是对应的 xi。
现在总指挥老师要求所有学生呈横队排列,部分同学需要移动到新的位置(新位置必须是整点),使得不存在两个同学站在同一个位置上。

为了节约时间,总指挥老师希望每个学生的移动距离的最大值尽可能小。请求出这个最小值。

输入格式

第一行:正整数 n,表示一共有多少位学生
第二行:n 个正整数 ai,表示每个班级的人数。
第三行n 个严格递增的整数xi,表示每队士兵的坐标。

输出格式

一行一个非负整数,表示每个同学的移动距离的最大值的最小值。

输入样例 复制

2
2 3
0 2

输出样例 复制

1

数据范围与提示

1 <= n <= 100,000 ,坐标在 int 范围内。