Vương quốc Byteland có ~N~ thành phố được đánh số từ ~1~ đến ~N~. Độ cao của thành phố thứ ~i~ là ~H_i~. Hệ thống giao thông của vương quốc gồm ~M~ con đường hai chiều đảm bảo giữa hai thành phố bất kì đều có thể đến được với nhau, mỗi con đường nối hai thành phố phân biệt. Hành trình của đoàn công tác đã chọn xuất phát từ thành phố ~1~ đi đến thành phố ~N~ sao cho chênh lệch độ cao lớn nhất giữa hai thành phố liên tiếp nhau trên đường đi là nhỏ nhất.

Yêu cầu: Tìm giá trị chênh lệch độ cao lớn nhất giữa hai thành phố liên tiếp nhau của hành trình mà đoàn công tác đã chọn.

Input

• Dòng đầu ghi ~2~ số nguyên ~N, M~ ~(N - 1 \le M \le 2 \times 10^5)~;

• Dòng thứ hai ghi ~N~ số nguyên lần lượt ~H_1, H_2, \dots, H_N~ ~(0 \le H_i \le 10^6)~;

• Trong ~M~ dòng tiếp theo, mỗi dòng ghi hai số nguyên ~u~ và ~v~ cho biết có một con đường nối giữa hai thành phố;

• Các số trong tệp ghi cách nhau ít nhất một dấu cách.

Output

Ghi một số duy nhất là giá trị chênh lệch tìm được.

Scoring

Sample Input 1

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

Sample Output 1

6

Notes

Hành trình đoàn công tác là: ~1 \rightarrow 2 \rightarrow 4~, chênh lệch độ cao lần lượt là:

• Từ ~1 \rightarrow 2~: ~|1 - 4| = 3~.

• Từ ~2 \rightarrow 4~: ~|4 - 10| = 6~.

Do đó kết quả là: ~\max(3, 6) = 6~.