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
#include<bits/stdc++.h>

int main(){
	using namespace std;
	ios::sync_with_stdio(false), cin.tie(nullptr);
	
	int64_t n, m, s;
	cin >> n >> m >> s;
	
	vector<pair<int64_t, int64_t>> ranges(m);
	for(auto &[l, r] : ranges){
		cin >> l >> r;
	}

	ranges.emplace_back(0, 0);
	ranges.emplace_back(n + 1, n + 1);
	const int64_t inf = (int64_t)1e18;
	int64_t best = inf;
	int64_t who = inf; // minimize best and after that who
	
	sort(ranges.begin(), ranges.end());
	
	auto Try = [&](int64_t p)->void{
		if(abs(p - s) <= best){
			if(abs(p - s) == best) who = min(who, p); 
			else who = p;
			best = abs(p - s);
		}
	};
	
	for(int i = 0;i < m + 1;i++){
		// [l, r] .. [l2, r2]
		auto [l1, r1] = ranges[i];
		auto [l2, r2] = ranges[i + 1];
		if(r1 + 1 < l2) Try(r1 + 1);
		if(l2 - 1 > r1) Try(l2 - 1);
	}
	
	cout << who << '\n';
	
	return 0;
}