最小差异题目描述 　　Bob 有 n 个数对，第 i 个是 (ai​,bi​)，同时有两个桶，初始都为空。 　　Bob 会对于i=1,2,⋯,n，依次选择 ai​,bi​ 中的恰好一个，并任意加入

　　题目描述lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　Bob 有 n 个数对，第 i 个是 (ai​,bi​)，同时有两个桶，初始都为空。lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　Bob 会对于i=1,2,⋯,n，依次选择 ai​,bi​ 中的恰好一个，并任意加入到他的任意一个桶中。lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　最终，Bob 的两个桶里必须都非空，他想要最小化两个桶中最大元素的差值，请求出这个值。lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　输入格式lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　第一行一个整数 n。lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　接下来 n 行，每行两个整数 ai​,bi​ 表示一个数对。lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　输出格式lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　一行一个整数表示答案。lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　数据范围lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　对于 30% 的数据，n≤18。lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　对于 60% 的数据，n≤1000。lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　对于 100% 的数据，22≤n≤2×10^5，1≤ai​,bi​≤10^9。lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　样例数据lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　输入:lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　2lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　1 6lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　4 9lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　输出:lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　2lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　说明:lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　在 (1,6) 中选择 6 放入桶 1lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　在 (4,9) 中选择 4 放入桶 2lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　两个桶最大元素的差值为 6-4=2。lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　输入:lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　2lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　1 9lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　4 6lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　输出:lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　3lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　说明:lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　在 (1,9) 中选择 9 放入桶 1lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　在 (4,6) 中选择 6 放入桶 2lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

　　两个桶最大元素的差值为 9-6=3。lvm100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库