1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
from sys import stdin, stdout

n, m, s = [int(s) for s in stdin.readline().split()]
zajete = []
for _ in range(m):
    blok = [int(s) for s in stdin.readline().split()]
    zajete.append(blok)

przed_szkola = []
za_szkola = []

for l, r in zajete:
    if s <= r:
        za_szkola.append([l, r])
    if s >= l:
        przed_szkola.append([l, r])

przed_szkola = sorted(przed_szkola, key=lambda x: -x[0])
output_przed = -1
i = 0
while i < len(przed_szkola):
    l, r = przed_szkola[i]
    if l == 1:
        # no space left here
        break
    # check if can take before it
    if (i == len(przed_szkola) - 1) or (l - 1 != przed_szkola[i + 1][1]):
        output_przed = l - 1
        break
    i += 1

za_szkola = sorted(za_szkola, key=lambda x: x[1])
output_za = -1
i = 0
while i < len(za_szkola):
    l, r = za_szkola[i]
    if r == n:
        # no space left here
        break
    #check if can take after it
    if (i == len(za_szkola) - 1) or (r + 1 != za_szkola[i + 1][0]):
        output_za = r + 1
        break
    i += 1

# print(przed_szkola)
# print(za_szkola)
# print(output_przed)
# print(output_za)

if output_przed == -1:
    output = output_za
elif output_za == -1:
    output = output_przed
else:
    dist_przed = s - output_przed
    dist_za = output_za - s
    if dist_przed > dist_za:
        output = output_za
    else:
        output = output_przed

stdout.write(str(output))