Finally! Vasya have come of age and that means he can finally get a passport! To do it, he needs to visit the passport office, but it's not that simple. There's only one receptionist at the passport office and people can queue up long before it actually opens. Vasya wants to visit the passport office tomorrow.

He knows that the receptionist starts working after t_{s} minutes have passed after midnight and closes after t_{f} minutes have passed after midnight (so that (t_{f} - 1) is the last minute when the receptionist is still working). The receptionist spends exactly t minutes on each person in the queue. If the receptionist would stop working within t minutes, he stops serving visitors (other than the one he already serves). 

Vasya also knows that exactly n visitors would come tomorrow. For each visitor Vasya knows the point of time when he would come to the passport office. Each visitor queues up and doesn't leave until he was served. If the receptionist is free when a visitor comes (in particular, if the previous visitor was just served and the queue is empty), the receptionist begins to serve the newcomer immediately. [Image] "Reception 1" 

For each visitor, the point of time when he would come to the passport office is positive. Vasya can come to the office at the time zero (that is, at midnight) if he needs so, but he can come to the office only at integer points of time. If Vasya arrives at the passport office at the same time with several other visitors, he yields to them and stand in the queue after the last of them.

Vasya wants to come at such point of time that he will be served by the receptionist, and he would spend the minimum possible time in the queue. Help him!


-----Input-----

The first line contains three integers: the point of time when the receptionist begins to work t_{s}, the point of time when the receptionist stops working t_{f} and the time the receptionist spends on each visitor t. The second line contains one integer n — the amount of visitors (0 ≤ n ≤ 100 000). The third line contains positive integers in non-decreasing order — the points of time when the visitors arrive to the passport office.

All times are set in minutes and do not exceed 10^12; it is guaranteed that t_{s} < t_{f}. It is also guaranteed that Vasya can arrive at the passport office at such a point of time that he would be served by the receptionist.


-----Output-----

Print single non-negative integer — the point of time when Vasya should arrive at the passport office. If Vasya arrives at the passport office at the same time with several other visitors, he yields to them and queues up the last. If there are many answers, you can print any of them.


-----Examples-----
Input
10 15 2
2
10 13

Output
12
Input
8 17 3
4
3 4 5 8

Output
2


-----Note-----

In the first example the first visitor comes exactly at the point of time when the receptionist begins to work, and he is served for two minutes. At 12 minutes after the midnight the receptionist stops serving the first visitor, and if Vasya arrives at this moment, he will be served immediately, because the next visitor would only come at 13 minutes after midnight.

In the second example, Vasya has to come before anyone else to be served.

Difficulty: HARD
Tags: Complete search

Greedy algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
def main():
	(start, end, t) = map(int, input().split())
	n = int(input())
	people = []
	if n != 0:
		people = list(map(int, input().split()))
	time = start
	ans = 1e+16
	answer = 0
	for p in people:
		if p + t > end:
			break
		if p - 1 >= 0:
			if ans > max(0, time - (p - 1)):
				ans = max(0, time - (p - 1))
				answer = p - 1
		time = max(time, p) + t
		if time + t > end:
			break
	if time + t <= end:
		answer = time
	print(answer)
main()


(s, e, t_per_v) = list(map(int, input().split()))
e -= t_per_v
n = int(input())
if n > 0:
	visitors = list(map(int, input().split()))
else:
	visitors = []
min_wait_time = float('inf')
min_arrive_time = -1
visitor_index = 0
t = s
while t <= e:
	if visitor_index >= len(visitors) or visitors[visitor_index] > t:
		print(t)
		exit(0)
	wait_time = t - visitors[visitor_index]
	if wait_time < min_wait_time:
		min_wait_time = wait_time
		min_arrive_time = visitors[visitor_index]
	t += t_per_v
	visitor_index += 1
print(min_arrive_time - 1)


(a, b, c) = [int(x) for x in input().split()]
n = int(input())
if n == 0:
	print(a)
	quit()
mas = [int(x) for x in input().split()]
m = 100000000000000.0
p = 0
for i in mas:
	if i <= b - c:
		if i and a - i + 1 < m:
			m = a - i + 1
			p = min(i - 1, a)
		a = max(a, i) + c
if a <= b - c:
	p = a
print(p)


import math
(start, finish, time) = map(int, input().split())
b = int(input())

def solve():
	firstAvailableSpot = start
	minimumTimeInQueue = 10 ** 12 + 1
	minimum = 23123
	last = 0
	for i in range(len(q)):
		if q[i] > firstAvailableSpot and firstAvailableSpot + time < finish:
			return firstAvailableSpot
		timeInQueue = firstAvailableSpot - q[i]
		firstAvailableSpot += time
		if q[i] != last:
			if timeInQueue + 1 < minimumTimeInQueue:
				minimumTimeInQueue = timeInQueue + 1
				minimum = q[i] - 1
				last = q[i]
		if firstAvailableSpot >= finish or len(q) - 1 == i:
			if firstAvailableSpot + time <= finish:
				return firstAvailableSpot
			return minimum
if b != 0:
	q = list(map(int, input().split()))
	print(solve())
else:
	print(str(start))


def update(t, l, ans):
	if l < ans[1]:
		ans[0] = t
		ans[1] = l

def solve():
	(S, E, L) = list(map(int, input().split()))
	n = int(input())
	if n == 0:
		return S
	a = list(map(int, input().split()))[::-1]
	if S < a[-1]:
		return S
	ans = [0, S]
	cur_t = S
	while cur_t + L <= E and len(a) > 0:
		if cur_t < a[-1]:
			return cur_t
		t = a.pop()
		update(t - 1, cur_t - t + 1, ans)
		cur_t += L
	if cur_t + L <= E:
		return cur_t
	return ans[0]
print(solve())


(ts, tf, t) = map(int, input().split())
n = int(input())
visitors = list(map(int, input().split())) if n else []
finish = [ts]
for visitor in visitors:
	finish.append(max(finish[-1], visitor) + t)
res = 0
min_time = 10 ** 13
for i in range(n):
	if finish[i] + t >= tf:
		continue
	if visitors[i] == 0:
		continue
	if max(0, finish[i] - (visitors[i] - 1)) < min_time:
		res = min(visitors[i] - 1, finish[i])
		min_time = max(0, finish[i] - (visitors[i] - 1))
if finish[-1] + t <= tf:
	res = finish[-1]
	min_time = 0
print(res)


import sys

def debug(x, table):
	for (name, val) in table.items():
		if x is val:
			print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
			return None

def solve():
	(ts, tf, t) = map(int, input().split())
	n = int(input())
	if n == 0:
		print(ts)
		return None
	AT = [int(i) for i in input().split()]
	BT = [0] * n
	for (i, at) in enumerate(AT):
		if i == 0:
			if at > ts:
				print(ts)
				return None
			else:
				BT[i] = ts
		elif at > BT[i - 1] + t and BT[i - 1] + t <= tf:
			print(BT[i - 1] + t)
			return None
		else:
			BT[i] = BT[i - 1] + t
	if BT[n - 1] + 2 * t <= tf:
		print(BT[n - 1] + t)
		return None
	min_wait = float('inf')
	ans = None
	for i in range(n):
		if i > 0 and AT[i] == AT[i - 1]:
			continue
		elif BT[i] - (AT[i] - 1) < min_wait and BT[i] + t <= tf:
			min_wait = BT[i] - (AT[i] - 1)
			ans = AT[i] - 1
	print(ans)

def __starting_point():
	solve()
__starting_point()


from sys import stdin
lines = stdin.readlines()
(current_free, f, t) = map(int, lines[0].split())
n = int(lines[1])
arrival_times = []
if n > 0:
	arrival_times = list(map(int, lines[2].split()))
min_wait = f
min_arrival = -1
current_free

def check_arrival_at(arrival):
	global min_arrival
	global min_wait
	global t
	global f
	if current_free + t <= f and arrival + t <= f:
		wait = current_free - max(0, arrival)
		if wait < min_wait:
			min_wait = wait
			min_arrival = arrival
for a in arrival_times:
	check_arrival_at(a - 1)
	if min_wait == 0:
		break
	current_free = current_free + t
	if current_free + t > f:
		break
check_arrival_at(current_free)
print(min_arrival)


import bisect
import sys
(ts, tf, T) = [int(x) for x in input().split()]
N = int(input())
if N == 0:
	print(ts)
	sys.exit()
Ts = [int(x) for x in input().strip().split()]
check_times = sorted(set([x - 1 for x in Ts + [Ts[-1] + 2] if x - 1 >= 0] + [ts]))
(best_waiting_time, best_time) = (float('inf'), -1)
last_waiting = None
all_times = []
for t in check_times:
	idx = bisect.bisect_right(Ts, t)
	if t < ts:
		wt_time = ts - t + idx * T
	elif last_waiting is not None:
		last_idx = last_waiting['idx']
		last_time = last_waiting['time']
		last_waiting_time = last_waiting['wt_time']
		wt_time = max(last_waiting_time + (idx - last_idx) * T - (t - last_time), 0)
	else:
		wt_time = idx * T
	if wt_time < best_waiting_time and t + wt_time <= tf - T:
		best_waiting_time = wt_time
		best_time = t
	last_waiting = {'idx': idx, 'time': t, 'wt_time': wt_time}
	all_times.append(last_waiting)
tail_end = last_waiting['time'] + last_waiting['wt_time']
if tail_end <= tf - T and best_waiting_time > 0:
	best_waiting_time = 0
	best_time = tail_end
print(best_time)


(a, b, c) = map(int, input().split())
n = int(input())
if n == 0:
	print(a)
	exit()
arr = [int(i) for i in input().split()]
(p, m) = (0, int(1e+18))
for i in arr:
	if i <= b - c:
		if i > 0 and a - i + 1 < m:
			m = a - i + 1
			p = min(i - 1, a)
		a = max(a, i) + c
print(a if a <= b - c else p)


f = lambda : map(int, input().split())
(a, b, t) = f()
(k,) = f()
s = d = 1000000000000.0
for q in f() if k else []:
	if q > a:
		s = a
	if q > a or a + t > b:
		break
	elif a - q < d:
		(s, d) = (q - 1, a - q)
	a += t
print(s if a + t > b else a)


INF = 10 ** 19
(ts, tf, t) = map(int, input().split())
n = int(input())
u = []
if n > 0:
	u = list(map(int, input().split()))
a = []
b = []
i = 0
while i < n:
	a.append(u[i])
	if i == 0:
		start = max(ts, u[i])
	else:
		start = max(b[-1], a[-1])
	ng = 1
	while i + 1 < n and u[i] == u[i + 1]:
		i += 1
		ng += 1
	end = start + ng * t
	b.append(end)
	i += 1
res = None
if n == 0:
	res = ts
else:
	res = a[0] - 1
	min_w = max(0, ts - a[0] + 1)
	m = len(a)
	for j in range(1, m):
		start = a[j] - 1
		stop = max(b[j - 1], start)
		w = stop - start
		if w < min_w:
			min_w = w
			if stop < tf:
				res = start
	for j in range(1, m):
		start = a[j]
		stop = b[j]
		w = stop - start
		if w < min_w:
			min_w = w
			if stop < tf:
				res = start
	if b[m - 1] <= tf - t:
		res = tf - t
	if ts < a[0]:
		res = ts
print(res)


import sys
from pprint import pprint

class Fun:

	def __init__(self, tStart, intercept):
		self.tStart = tStart
		self.intercept = intercept

	def calcTime(self, time):
		return self.intercept - time
strings = sys.stdin.readlines()
(ts, tf, t) = [int(i) for i in strings[0].strip().split()]
n = int(strings[1].strip())
if n == 0:
	print(ts)
	exit(0)
customers = [int(i) for i in strings[2].strip().split()]
funs = dict()
funs[0] = Fun(tStart=0, intercept=ts + t)
lastFun = funs[0]
for cust in customers:
	if cust > tf:
		continue
	if lastFun.tStart == cust:
		lastFun.intercept += t
	else:
		funs[cust] = Fun(tStart=cust, intercept=lastFun.intercept + t)
	lastFun = funs[cust]
sortedTimes = sorted(customers, reverse=True)
prevIntercept = 0
for i in sortedTimes:
	if i < tf - t + 1:
		prevIntercept = funs[i].intercept
		break
if tf - t + 1 not in funs:
	funs[tf - t + 1] = Fun(tStart=tf - t + 1, intercept=prevIntercept)
minWait = 10 ** 12
minTime = 0
prevK = sorted(funs.keys())[0]
for i in sorted(funs.keys())[1:]:
	time = funs[i].tStart - 1
	wait = funs[prevK].calcTime(time)
	if wait < minWait and time + wait <= tf:
		minWait = wait
		minTime = time
	prevK = i
print(minTime)


[ts, tf, t] = list(map(int, input().split()))
n = int(input())
if n == 0:
	print(ts)
	exit(0)
a = list(map(int, input().split()))
if a[0] > ts:
	print(ts)
	exit(0)
min_wait = 1e+18
tbest = a[0] - 1
tnow = ts
twait = tnow - tbest
min_wait = min(min_wait, twait)
i = 0
while i < n:
	tnow = max(tnow, a[i])
	j = i
	while j < n and a[j] == a[i]:
		j += 1
	tnow += (j - i) * t
	if j == n:
		break
	tcome = a[j] - 1
	twait = tnow - tcome
	if twait < min_wait and tcome + t <= tf:
		min_wait = twait
		tbest = tcome
	i = j
if tnow + t <= tf:
	print(tnow)
else:
	print(tbest)


(begin, end, time) = list(map(int, input().split()))
n = int(input())
if n == 1:
	print(begin)
elif n > 0:
	ar = list(map(int, input().split()))
	ar.sort()
	i = 0
	ar.append(end - time + 1)
	n += 1
	num = begin
	ans = begin - ar[0] + 1
	fin_ans = ar[0] - 1
	while i < n:
		num = max(num + time, ar[i] + time)
		while i + 1 < n and ar[i + 1] == ar[i]:
			i += 1
			num += time
		i += 1
		if i < n and num - ar[i] + 1 < ans and (max(ar[i] - 1, num) + time <= end):
			ans = num - ar[i] + 1
			fin_ans = ar[i] - 1
	print(fin_ans)
else:
	print(begin)


import sys
(t1, t2, t) = map(int, input().split())
u = 1
n = int(input())
if n == 0:
	print(t1)
	sys.exit()
a = [int(i) for i in input().split()]
mini = 10 ** 20
ans = 0
time = t1
for x in a:
	if x <= t2 - t:
		if time - x + 1 < mini and x > 0:
			mini = time - x + 1
			if x - 1 > time:
				ans = time
			else:
				ans = x - 1
		time = t + max(time, x)
if time > t2 - t:
	print(ans)
else:
	print(time)


from collections import Counter
(ts, tf, t) = list(map(int, input().split()))
n = int(input())
if n == 0:
	print(ts)
	exit(0)
tp = list(map(int, input().split()))
c = Counter(tp + [tf - t + 1])
(ans, time) = (-1, 10 ** 13)
wt = ts
times = sorted(c.keys())
for i in times:
	wt = max(wt, i - 1)
	if time > wt - i + 1:
		time = wt - i + 1
		ans = i - 1
	wt += c[i] * t
	if wt > tf - t + 1:
		break
print(ans)


def ri():
	return map(int, input().split())
(s, f, t) = ri()
n = int(input())
if n == 0:
	print(s)
	exit()
i = list(ri())
p = 0
a = s
m = 10 ** 100
for ii in i:
	if ii <= f - t:
		if a - ii + 1 < m:
			m = a - ii + 1
			p = min(ii - 1, a)
		a = max(a, ii) + t
if a <= f - t:
	p = a
print(p)


import sys
from array import array
from typing import List, Tuple, TypeVar, Generic, Sequence, Union

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	from collections import deque
	(ts, tf, t) = map(int, input().split())
	n = int(input())
	a = list(map(int, input().split()))[::-1]
	point = sorted((set(a) | set((x - 1 for x in a)) | {0, tf - t}) - {-1}) + [10 ** 18]
	(ans, wait) = ([-1], [10 ** 18])
	dq = deque()

	def end():
		print(ans, wait, dq, file=sys.stderr)
		print(ans[0])
		exit()

	def refresh(time):
		if (time if not dq else dq[-1]) + t > tf:
			end()
		if not dq:
			if time < ts:
				if ts - time < wait[0]:
					ans[0] = time
					wait[0] = ts - time
			else:
				ans[0] = time
				end()
		elif dq[-1] - time < wait[0]:
			ans[0] = time
			wait[0] = dq[-1] - time
	for (i, p) in enumerate(point[:-1]):
		while a and a[-1] == p:
			dq.append(max(dq[-1] if dq else p, ts) + t)
			a.pop()
		refresh(p)
		while dq and dq[0] < point[i + 1]:
			cur = dq.popleft()
			refresh(cur)
	end()
main()


(ts, tf, t) = map(int, input().split())
n = int(input())
if n == 0:
	print(ts)
	exit()
vis = list(map(int, input().split()))
ans = min(vis[0] - 1, ts)
wt = ts - ans
cur = max(vis[0], ts)
for i in range(1, n):
	if vis[i] == vis[i - 1]:
		cur += t
	elif cur + t + t <= tf:
		if wt > cur + t - (vis[i] - 1):
			ans = min(cur + t, vis[i] - 1)
			wt = cur + t - ans
		cur = max(cur + t, vis[i])
	else:
		break
if cur + t + t <= tf:
	print(tf - t)
else:
	print(ans)


inp = input().split(' ')
ts = int(inp[0])
tf = int(inp[1])
T = int(inp[2])
inp = input()
n = int(inp)
if n == 0:
	print(ts)
else:
	inp = input().split(' ')
	min_del_t = 10000000000000
	ans = int(inp[0]) - 1
	t_cur = ts
	for tS in inp:
		t = int(tS)
		time_waiting = t_cur - t + 1
		if t_cur < t and t_cur + T <= tf:
			ans = t_cur
			break
		elif min_del_t > time_waiting and t_cur + T <= tf:
			min_del_t = time_waiting
			ans = t - 1
		t_cur += T
	if t_cur + T <= tf:
		print(t_cur)
	else:
		print(ans)


import math
import sys
(arrival, departure, time_per_client) = [int(x) for x in input().split()]
num_clients = int(input())
if num_clients > 0:
	clients_arrival = [int(x) for x in input().split()]
else:
	print(arrival)
	sys.exit()
best_time = None
current_time = arrival
clients_at_queue = 0
client_to_arrive = 0
client_wait_time = [math.inf for client in clients_arrival]
client_to_leave = 0
while current_time <= departure - time_per_client:
	while client_to_arrive < num_clients and clients_arrival[client_to_arrive] <= current_time:
		clients_at_queue += 1
		client_to_arrive += 1
	if clients_at_queue == 0:
		best_time = current_time
		break
	else:
		clients_at_queue -= 1
		client_wait_time[client_to_leave] = current_time - clients_arrival[client_to_leave]
		client_to_leave += 1
		current_time += time_per_client
while (best_time is None or best_time < 0) and len(client_wait_time) > 0:
	happiest_client = client_wait_time.index(min(client_wait_time))
	best_time = clients_arrival[happiest_client] - 1
	if best_time < 0:
		client_wait_time = client_wait_time[happiest_client + 1:]
		clients_arrival = clients_arrival[happiest_client + 1:]
print(best_time)


(ts, tf, te) = map(int, input().split(' '))
n = int(input())
if n == 0:
	print(ts)
	exit(0)
arr = list(map(int, input().split(' ')))
idx = 0
curr_time = ts
wait_time = max(0, ts - arr[0] + 1)
ans = min(arr[0] - 1, ts)
while wait_time > 0:
	curr_time += te
	idx += 1
	if idx == n or curr_time >= tf:
		break
	next_wait = max(0, curr_time - arr[idx] + 1)
	if next_wait < wait_time:
		wait_time = next_wait
		ans = arr[idx] - 1
if wait_time > 0 and curr_time + te <= tf:
	ans = curr_time
print(ans)


from math import floor
(s, f, k) = input().split()
s = int(s)
f = int(f)
k = int(k)
n = int(input())
w = []
t = []
if n > 0:
	a = list(map(int, input().split()))
	te = s
	diff = f - s
	m = floor(diff / k)
	if n < m:
		m = n
	if a[0] != 0:
		w.append(a[0] - 1)
		t.append(s)
	p = 0
	for i in range(m):
		if a[i] - a[p] > k:
			w.append(a[i] - 1)
			t.append(te - (a[i] - 1))
		p = i
		te += k
	if te <= f - k:
		w.append(te)
		t.append(0)
	min = 0
	for ww in range(len(w)):
		if t[ww] < t[min]:
			min = ww
	print(w[min])
else:
	print(s)


(ts, tf, t) = map(int, input().split())
n = int(input())
INF = int(10 ** 18)
if n == 0:
	print(ts)
	quit()
a = list(map(int, input().split()))
i = 0
ans = -1
best = INF
end = ts
dif = 0

def checkans(curans, time):
	global ans, best
	if curans < best and time + max(curans, 0) + t <= tf:
		ans = time
		best = curans
while i < n:
	dif = t
	pri = i - 1
	while i + 1 < n and a[i] == a[i + 1]:
		dif += t
		i += 1
	if pri < 0 or a[pri] != a[i] - 1:
		checkans(end - (a[i] - 1), a[i] - 1)
	end += dif
	curans = end - a[i]
	checkans(end - a[i], a[i])
	i += 1
checkans(0, end)
print(ans)