雀士分组

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

sdut雀士联盟中有许多水平各异的职业雀士,现在为了参加即将举办的神仙杯麻将比赛,联盟决定将所有雀士分为两队(碰精队和杠精队)分开举行训练赛。为了方便分组,联盟对每一位选手进行了雀力评估,对第i个雀士的评估得分为Ai。联盟出于对于雀士的心态考虑决定将实力相近的雀士分为一组,即让max(碰精队max - 碰精队min, 杠精队max - 杠精队min) 的值 最小(其中碰精队max代表碰精队中最高那位的雀力数值,其他同理)。不过联盟中部分雀士由于打法原因和一些其他雀士关系恶劣,绝对不能分在一组之内。分组方案的结果可以使一组人的人数为 0。

Input

第一行一个N(1 <= N <= 100000)代表联盟中一共有N名雀士,雀士编号由1至N。 
第二行输入N个整数Ai(1 <= Ai <= 100000000),代表第i名雀士雀力评估得分。 
接下来输入1个整数M(0 <= M <= 100000),代表有M组雀士关系恶劣,不能分进同一组。 
接下来输入M行x, y(1 <= x, y <= N),代表编号为x的和编号为y的雀士关系恶劣, 保证不会重复输入雀士关系。

Output

假如没有办法将所有的雀士分成两队,输出 “impossible”(输出不包括引号),否则输出最小的max(碰精队max - 碰精队min, 杠精队max - 杠精队min)。

Sample Input

10 
1 6 4 2 8 9 21 15 7 19 
3 
7 1 
2 10 
8 10

Sample Output

14

Hint

Source

Ransln