import sys
from collections import defaultdict
from heapq import heappush, heappop
# Performance Test
class Treap:
def __init__(self):
self.root = 0
self.left = [0]
self.right = [0]
self.children = [self.left, self.right]
self.key = [0]
self.priority = [0]
self.count = [0]
self.deleted = set()
self.rand = self.xor128()
def xor128(self):
x = 123456789
y = 362436069
z = 521288629
w = 88675123
while True:
t, x, y, z = x ^ ((x << 11) & 0xffffffff), y, z, w
w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))
yield w
def get_size(self):
return self.count[self.root]
def _merge(self, li, ri):
left = self.left
right = self.right
children = self.children
priority = self.priority
count = self.count
stack = []
while li != 0 and ri != 0:
if priority[li] > priority[ri]:
stack.append((li, 1))
li = right[li]
else:
stack.append((ri, 0))
ri = left[ri]
vi = li if li != 0 else ri
for pi, d in reversed(stack):
children[d][pi] = vi
count[pi] = count[left[pi]] + count[right[pi]] + 1
vi = pi
return vi
def _split_by_key(self, vi, x):
"""
:return: (LeftRoot, RightRoot)
LeftRoot: Root node of the split tree consisting of nodes with key < x.
RightNode: Root node of the split tree consisting of nodes with key >= x.
"""
left = self.left
right = self.right
key = self.key
count = self.count
l_stack = []
r_stack = []
while vi != 0:
if x < key[vi]:
r_stack.append(vi)
vi = left[vi]
else:
l_stack.append(vi)
vi = right[vi]
li, ri = 0, 0
for pi in reversed(l_stack):
right[pi] = li
count[pi] = count[left[pi]] + count[li] + 1
li = pi
for pi in reversed(r_stack):
left[pi] = ri
count[pi] = count[ri] + count[right[pi]] + 1
ri = pi
return li, ri
def insert(self, x):
left = self.left
right = self.right
children = self.children
key = self.key
priority = self.priority
count = self.count
np = next(self.rand)
if self.deleted:
ni = self.deleted.pop()
left[ni] = 0
right[ni] = 0
key[ni] = x
priority[ni] = np
count[ni] = 1
else:
ni = len(self.key)
left.append(0)
right.append(0)
key.append(x)
priority.append(np)
count.append(1)
vi = self.root
pi = 0
d = 0
while vi != 0:
if np > priority[vi]:
li, ri = self._split_by_key(vi, x)
left[ni] = li
right[ni] = ri
count[ni] = count[li] + count[ri] + 1
break
pi = vi
d = int(x >= key[vi])
count[vi] += 1
vi = children[d][vi]
if pi == 0:
self.root = ni
else:
children[d][pi] = ni
def delete(self, x):
left = self.left
right = self.right
children = self.children
key = self.key
count = self.count
vi = self.root
pi = 0
d = 0
while vi != 0:
if key[vi] == x:
self.deleted.add(vi)
vi = self._merge(left[vi], right[vi])
break
pi = vi
d = int(x >= key[vi])
count[vi] -= 1
vi = children[d][vi]
if pi == 0:
self.root = vi
else:
children[d][pi] = vi
def upper_bound(self, x):
"""
:return (Node, i)
Node: with the smallest key y satisfying x < y.
i: 0-indexed order.
If same keys exist, return leftmost one.
If not exists, return (None, n).
"""
left = self.left
right = self.right
key = self.key
count = self.count
vi = self.root
ti = 0
i = count[vi]
j = 0
while vi != 0:
if x < key[vi]:
ti = vi
i = j + count[left[vi]]
vi = left[vi]
else:
j += count[left[vi]] + 1
vi = right[vi]
return ti, i
def lower_bound(self, x):
"""
:return (Node, i)
Node: with the smallest key y satisfying x <= y.
i: 0-indexed order.
If same keys exist, return leftmost one.
If not exists, return (None, n).
"""
left = self.left
right = self.right
key = self.key
count = self.count
vi = self.root
ti = 0
i = count[vi]
j = 0
while vi != 0:
if x <= key[vi]:
ti = vi
i = j + count[left[vi]]
vi = left[vi]
else:
j += count[left[vi]] + 1
vi = right[vi]
return ti, i
def get_by_index(self, i):
"""
:return (0-indexed) i-th smallest node.
If i is greater than length, None will be returned.
"""
left = self.left
right = self.right
count = self.count
if i < 0 or self.get_size() <= i:
return 0
vi = self.root
j = i
while vi != 0:
l_cnt = count[left[vi]]
if l_cnt == j:
return vi
if j < l_cnt:
vi = left[vi]
else:
j -= l_cnt + 1
vi = right[vi]
assert False, 'Unreachable'
def get_max(self):
# 多くの場合において処理が単純な分 get_by_index(get_size - 1) より速いが、
# テストケースによっては途中で処理を打ち切れる get_by_index の方が速いことがある
right = self.right
vi = self.root
if vi == 0:
return 0
while right[vi] != 0:
vi = right[vi]
return vi
def get_next(self, i, vi):
"""
:return: next node of i-th "node". (= (i+1)th node)
"""
# If node has right child, the root-node search can be omitted.
# Otherwise, get_by_index(i+1).
left = self.left
right = self.right
if vi == 0:
return 0
if right[vi] == 0:
return self.get_by_index(i + 1)
vi = right[vi]
while left[vi] != 0:
vi = left[vi]
return vi
def get_prev(self, i, vi):
left = self.left
right = self.right
if vi == 0:
return 0
if left[vi] == 0:
return self.get_by_index(i - 1)
vi = left[vi]
while right[vi] != 0:
vi = right[vi]
return vi
def debug_print(self):
self._debug_print(self.root, 0)
def _debug_print(self, vi, depth):
if vi != 0:
self._debug_print(self.left[vi], depth + 1)
print(' ' * depth, self.key[vi], self.priority[vi], self.count[vi])
self._debug_print(self.right[vi], depth + 1)
def dist_insert(x):
heappush(dists, x)
available_dists[x] += 1
def dist_delete(x):
available_dists[x] -= 1
def dist_get_min():
while dists and available_dists[dists[0]] == 0:
heappop(dists)
if dists:
return dists[0]
return 0xffffffff
n, l, x = map(int, input().split())
aaa = list(map(int, sys.stdin))
trp1 = Treap()
dists = []
available_dists = defaultdict(lambda: 0)
trp1key = trp1.key
strawberry = {x}
trp1.insert(min(x, l - x))
buf = []
for a in aaa:
b = min(a, l - a)
if a in strawberry:
vi, i = trp1.lower_bound(b)
li1 = trp1.get_prev(i, vi)
li2 = trp1.get_prev(i - 1, li1)
ri1 = trp1.get_next(i, vi)
ri2 = trp1.get_next(i + 1, ri1)
l1, l2, r1, r2 = trp1key[li1], trp1key[li2], trp1key[ri1], trp1key[ri2]
if li2 != 0:
dist_delete(b - l2)
if ri1 != 0:
dist_insert(r1 - l2)
if ri2 != 0:
dist_delete(r2 - b)
if li1 != 0:
dist_insert(r2 - l1)
if li1 != 0 and ri1 != 0:
dist_delete(r1 - l1)
strawberry.remove(a)
trp1.delete(b)
else:
strawberry.add(a)
trp1.insert(b)
vi, i = trp1.lower_bound(b)
li1 = trp1.get_prev(i, vi)
li2 = trp1.get_prev(i - 1, li1)
ri1 = trp1.get_next(i, vi)
ri2 = trp1.get_next(i + 1, ri1)
l1, l2, r1, r2 = trp1key[li1], trp1key[li2], trp1key[ri1], trp1key[ri2]
if li2 != 0:
dist_insert(b - l2)
if ri1 != 0:
dist_delete(r1 - l2)
if ri2 != 0:
dist_insert(r2 - b)
if li1 != 0:
dist_delete(r2 - l1)
if li1 != 0 and ri1 != 0:
dist_insert(r1 - l1)
size = trp1.get_size()
ci2 = trp1.get_by_index(size - 1)
ci1 = trp1.get_prev(size - 1, ci2)
buf.append(min(dist_get_min(), l - trp1key[ci1] - trp1key[ci2]))
print(*buf)