Partitioning Sequence into Two Multisets

Given a sequence (v) of length (n), partition it into two multisets (A) and (B) as you process the sequence from left to right. Every number must be placed in at least one multiset. A number (v_i) can be placed in (A) if and only if for every index (j < i) such that (v_j \le v_i - k) it holds that (v_j) has not been placed in (A); equivalently, if (A) is nonempty with current minimum value (a_{min}), then it must be that (v_i < a_{min} + k). Similarly, (v_i) can be placed in (B) if and only if for every index (j < i) with (v_j \ge v_i + k) one has that (v_j) is not in (B); if (B) is nonempty with current maximum value (b_{max}), then (v_i) can be added only if (b_{max} < v_i + k).

In addition, there are (m) pairs of indices provided. For each forbidden pair ((u, v)), the numbers at these indices must not be placed together in the same multiset (i.e. they cannot both be in (A) or both in (B)). Note that a number may be placed in both multisets; however, doing so means it participates in both sets and hence contributes to the conditions of both.

Your task is to find the minimum nonnegative integer (k) such that there exists a valid left-to-right assignment for all elements of (v) satisfying the above conditions. If no such assignment exists, output -1.

Note on the conditions:

• If \(A\) is empty, a number can always be assigned to \(A\); otherwise, if the current minimum among numbers in \(A\) is \(a_{min}\), then a new number \(v_i\) can be added to \(A\) only if \(v_i < a_{min} + k\). When \(v_i\) is added to \(A\), update \(a_{min}\) to \(\min(a_{min}, v_i)\).
• If \(B\) is empty, a number can always be assigned to \(B\); otherwise, if the current maximum among numbers in \(B\) is \(b_{max}\), then a new number \(v_i\) can be added to \(B\) only if \(b_{max} < v_i + k\). When \(v_i\) is added to \(B\), update \(b_{max}\) to \(\max(b_{max}, v_i)\).
• The forbidden pair constraints ensure that for each forbidden pair \((u, v)\), \(v_u\) and \(v_v\) are not both assigned into \(A\) and are not both assigned into \(B\). (Note that if one number is assigned to both sets and the other to one set, they would share a common set, which is not allowed.)

inputFormat

The input begins with a line containing two integers \(n\) and \(m\), where \(n\) is the length of the sequence and \(m\) is the number of forbidden pairs.

The second line contains \(n\) space‐separated integers representing the sequence \(v\).

Each of the next \(m\) lines contains two integers \(u\) and \(v\) (1-indexed) indicating that the numbers at positions \(u\) and \(v\) must not be assigned to the same multiset.

outputFormat

Output the minimum nonnegative integer \(k\) such that a valid partition exists. If no valid partition exists, output -1.

sample

3 1
1 2 3
1 3

2