Warning: session_start(): open(/tmp/sess_2c6b70e788a04cd35b0ac17d595686d9, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
#include
#include
#include
#include
#define IL inline
using namespace std;
constexpr int MN(1e6+7);
template
class STree
{
private:
static constexpr xint ROOT = 1;
struct Node
{
xint l, r;
sint max, lza;
} t[MN << 2];
xint ll, rr, pos;
vint vv;
#define li i<<1
#define ri i<<1|1
#define t_mid ((t[i].l+t[i].r) >> 1)
#define add_v(i, v) ({t[i].max += v, t[i].lza += v;})
#define pd(i) \
({ \
if (t[i].lza) \
{ \
add_v(li, t[i].lza); \
add_v(ri, t[i].lza); \
t[i].lza = 0; \
} \
})
void build(const xint i, const xint l, const xint r)
{
t[i].l = l, t[i].r = r, t[i].lza = 0;
if (l == r)
t[i].max = 0;
else
{
build(li, l, t_mid),
build(ri, t_mid+1, r);
t[i].max = max(t[li].max, t[ri].max);;
}
}
void add(const xint i)
{
if (ll <= t[i].l && t[i].r <= rr) add_v(i, vv);
else
{
pd(i);
if (ll <= t_mid)
add(li);
if (rr > t_mid)
add(ri);
t[i].max = max(t[li].max, t[ri].max);;
}
}
public:
IL void build(const xint l, const xint r)
{
build(ROOT, l, r);
}
IL void add(const xint l, const xint r, const vint v)
{
ll = l, rr = r, vv = v,
add(ROOT);
}
IL sint gmax()
{
return t[ROOT].max;
}
};
int tr[MN];
STree st;
struct Node
{
int l, r, len;
IL bool operator <(const Node &o) const
{
return len < o.len;
}
} a[MN];
vector vals;
#define ID(x) lower_bound(vals.begin(), vals.end(), x)-vals.begin()
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for (int i=0; i= m)
{
ans = min(ans, a[r].len - a[l].len);
st.add(a[l].l, a[l].r, -1);
++l;
}
++r;
}
if (ans == INT_MAX)
puts("-1");
else
printf("%d", ans);
return 0;
}