Petya and Vasya got employed as couriers. During the working day they are to deliver packages to n different points on the line. According to the company’s internal rules, the delivery of packages must be carried out strictly in a certain order. Initially, Petya is at the point with the coordinate s 1, Vasya is at the point with the coordinate s 2, and the clients are at the points x 1, x 2, …, x n in the order of the required visit.
The guys agree in advance who of them will deliver the package to which of the customers, and then they act as follows. When the package for the i-th client is delivered, the one who delivers the package to the (i + 1)-st client is sent to the path (it can be the same person who went to the point x i, or the other). The friend who is not busy in delivering the current package, is standing still.
To communicate with each other, the guys have got walkie-talkies. The walkie-talkies work rather poorly at great distances, so Petya and Vasya want to distribute the orders so that the maximum distance between them during the day is as low as possible. Help Petya and Vasya to minimize the maximum distance between them, observing all delivery rules.
Input
The first line contains three integers n, s 1, s 2 (1 ≤ n ≤ 100 000, 0 ≤ s 1, s 2 ≤ 109) — number of points of delivery and starting positions of Petya and Vasya.
The second line contains n integers x 1, x 2, …, x n — customers coordinates (0 ≤ x i ≤ 109), in the order to make a delivery.
It is guaranteed, that among the numbers s 1, s 2, x 1, …, x n there are no two equal.
Output
Output the only integer, minimum possible maximal distance between couriers during delivery.
Examples
input
2 0 10
5 6
output
10
input
3 2 1
3 4 5
output
1
input
1 4 5
2
output
2
Note
In the first test case the initial distance between the couriers is 10. This value will be the answer, for example, Petya can perform both deliveries, and Vasya will remain at the starting point.
In the second test case you can optimally act, for example, like this: Vasya delivers the package to the first customer, Petya to the second and, finally, Vasya delivers the package to the third client. With this order of delivery, the distance between the couriers will never exceed 1.
In the third test case only two variants are possible: if the delivery of a single package is carried out by Petya, the maximum distance between them will be 5 - 2 = 3. If Vasya will deliver the package, the maximum distance is 4 - 2 = 2. The latter method is optimal.
Solution:
#include <bits/stdc++.h>
using namespace std;
class segtree {
public:
struct node {
// don't forget to set default value (used for leaves)
// not necessarily neutral element!
int mx = -1;
int mn = -1;
void apply(int l, int r, int v) {
mx = mn = v;
}
};
node unite(const node &a, const node &b) const {
node res;
res.mn = min(a.mn, b.mn);
res.mx = max(a.mx, b.mx);
return res;
}
inline void push(int x, int l, int r) {
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
// push from x into (x + 1) and z
/*
if (tree[x].add != 0) {
tree[x + 1].apply(l, y, tree[x].add);
tree[z].apply(y + 1, r, tree[x].add);
tree[x].add = 0;
}
*/
}
inline void pull(int x, int z) {
tree[x] = unite(tree[x + 1], tree[z]);
}
int n;
vector<node> tree;
void build(int x, int l, int r) {
if (l == r) {
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
build(x + 1, l, y);
build(z, y + 1, r);
pull(x, z);
}
template <typename M>
void build(int x, int l, int r, const vector<M> &v) {
if (l == r) {
tree[x].apply(l, r, v[l]);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
build(x + 1, l, y, v);
build(z, y + 1, r, v);
pull(x, z);
}
node get(int x, int l, int r, int ll, int rr) {
if (ll <= l && r <= rr) {
return tree[x];
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
push(x, l, r);
node res{};
if (rr <= y) {
res = get(x + 1, l, y, ll, rr);
} else {
if (ll > y) {
res = get(z, y + 1, r, ll, rr);
} else {
res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
}
}
pull(x, z);
return res;
}
template <typename... M>
void modify(int x, int l, int r, int ll, int rr, M... v) {
if (ll <= l && r <= rr) {
tree[x].apply(l, r, v...);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
push(x, l, r);
if (ll <= y) {
modify(x + 1, l, y, ll, rr, v...);
}
if (rr > y) {
modify(z, y + 1, r, ll, rr, v...);
}
pull(x, z);
}
function<bool(const node&)> f;
int find_first(int x, int l, int r, int ll, int rr, bool know) {
if (!know && ll <= l && r <= rr) {
if (!f(tree[x])) {
return -1;
}
know = true;
}
if (know && l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res = -1;
if (ll <= y && (!know || f(tree[x + 1]))) {
res = find_first(x + 1, l, y, ll, rr, know);
}
if (rr > y && res == -1) {
res = find_first(z, y + 1, r, ll, rr, know);
}
pull(x, z);
return res;
}
int find_last(int x, int l, int r, int ll, int rr, bool know) {
if (!know && ll <= l && r <= rr) {
if (!f(tree[x])) {
return -1;
}
know = true;
}
if (know && l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res = -1;
if (rr > y && (!know || f(tree[z]))) {
res = find_last(z, y + 1, r, ll, rr, know);
}
if (ll <= y && res == -1) {
res = find_last(x + 1, l, y, ll, rr, know);
}
pull(x, z);
return res;
}
segtree(int n) : n(n) {
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1);
}
template <typename M>
segtree(const vector<M> &v) {
n = v.size();
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1, v);
}
node get(int ll, int rr) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
return get(0, 0, n - 1, ll, rr);
}
template <typename... M>
void modify(int ll, int rr, M... v) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
modify(0, 0, n - 1, ll, rr, v...);
}
// find_first and find_last call all FALSE elements
// to the left (right) of the sought position exactly once
int find_first(int ll, int rr, const function<bool(const node&)> &ff) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
f = ff;
return find_first(0, 0, n - 1, ll, rr, false);
}
int find_last(int ll, int rr, const function<bool(const node&)> &ff) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
f = ff;
return find_last(0, 0, n - 1, ll, rr, false);
}
};
int main() {
int n, s1, s2;
scanf("%d %d %d", &n, &s1, &s2);
n += 2;
vector<int> x(n);
x[0] = s1;
x[1] = s2;
for (int i = 2; i < n; i++) {
scanf("%d", &x[i]);
}
segtree st(x);
int low = abs(s1 - s2), high = (int) 1e9;
while (low < high) {
int mid = (low + high) >> 1;
bool found = false;
int up = 0;
for (int i = 0; i < n - 1; i++) {
if (abs(x[i] - x[i + 1]) > mid) {
continue;
}
if (i > up) {
break;
}
int xi = x[i];
int nxt = st.find_first(i + 1, n - 1, [&mid, &xi](const auto &t) {
return (t.mx > xi + mid || t.mn < xi - mid);
});
if (nxt == -1) {
found = true;
break;
} else {
up = max(up, nxt - 1);
}
}
if (found) {
high = mid;
} else {
low = mid + 1;
}
}
printf("%d\n", low);
return 0;
}
