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\leq M\leq 2\times 10^5)\);
• Dòng thứ hai ghi \(N\) số nguyên lần lượt \(H_1,\ H_2,\ldots ,\ H_N\ (0\leq H_i\leq 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: Một số duy nhất là giá trị chênh lệch tìm được.

Ràng buộc:

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm của bài thỏa mãn: \(1 < N\leq 10\);
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm của bài thỏa mãn: \(10 < N\leq 100,\ H_i\leq 100\);
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm của bài thỏa mãn: \(100 < N\leq 10^5\).

Ví dụ:

SAMPLE INPUT

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

SAMPLE OUTPUT

6

Giải thích: Hành trình đoàn công tác là: \(1\to 2\to 4\), chênh lệch độ cao lần lượt là:

• Từ \(1\to 2:\ |1 - 4| = 3\)
• Từ \(2\to 4:\ |4 - 10| = 6\) Do đó kết quả là: max⁡\((3,\ 6) = 6\)