You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给你一个长度为 $n$ 的数列 $v$，请你将其划分成两个可重集 $a$ 和 $b$。你将从左至右开始划分，每个数必须至少被划分进一个可重集中。
一个数 $v_i$ 可以被划分进 $a$ 当且仅当 $j<i \ and\ v_j\le v_i-k$ 的 $v_j$ 都没有被划分进当前的 $a$。一个数 $v_i$ 可以被划分进 $b$ 当且仅当 $j<i\ and\ v_j\ge v_i+k$ 的 $v_j$ 都没有被划分进当前的 $b$。
同时给出了 $m$ 组关系，每组关系代表 $u$ 和 $v$ 不能划分进同一个可重集里。求能使划分成功的最小的 $k$。如果不存在合法划分，请输出 -1。

输入格式

第一行两个数 $n,m$，意义在题目描述中。
接下来一行共 $n$ 个数，代表 $v$。
下面 $m$ 行每行两个数，表示一组关系。

输出格式

仅一个数，答案。

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

提示

样例解释

样例解释一

以下是一组合法的划分：
|6|2|8|5|7|3| |:---:|:---:|:---:|:---:|:---:|:---:| |a|b|b|a|b|a|

样例解释二

以下是一组合法的划分：
|1|3|4|3|8|2|3|4|5|6| |:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:| |b|b|a|b|a|b|a|a|a|b|

数据范围

对于 $100\%$ 的数据，$n,m\le2\times10^4,v_i\le10^9$，保证 $u<v\le n$，没有一对相同的 $u,v$。