Description

You are given a sequence $v$ of length $n$. Please partition it into two multisets $a$ and $b$. You will partition from left to right, and each number must be put into at least one multiset.

A number $v_i$ can be put into $a$ if and only if all $v_j$ with $j<i \ and\ v_j\le v_i-k$ have not been put into the current $a$.

A number $v_i$ can be put into $b$ if and only if all $v_j$ with $j<i\ and\ v_j\ge v_i+k$ have not been put into the current $b$.

At the same time, $m$ pairs of relations are given. Each relation means that $u$ and $v$ cannot be put into the same multiset. Find the minimum $k$ that makes a successful partition possible. If no valid partition exists, output -1.

Input Format

The first line contains two integers $n,m$, as described in the statement.
The next line contains $n$ integers, representing $v$.
The following $m$ lines each contain two integers, representing one relation.

Output Format

Output one integer, the answer.

6 0
6 2 8 5 7 3

2

10 3
1 3 4 3 8 2 3 4 5 6
2 3
6 7
1 9

5

Hint

Sample Explanation

Sample Explanation 1

The following is one valid partition:
|6|2|8|5|7|3| |:---:|:---:|:---:|:---:|:---:|:---:| |a|b|b|a|b|a|

Sample Explanation 2

The following is one valid partition:
|1|3|4|3|8|2|3|4|5|6| |:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:| |b|b|a|b|a|b|a|a|a|b|

Constraints

For $100\%$ of the testdata, $n,m\le2\times10^4$ and $v_i\le10^9$. It is guaranteed that $u<v\le n$, and there are no duplicate pairs $(u,v)$.

Translated by ChatGPT 5