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
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <vector>

class Range {
public:
  long long start;
  long long end;

  Range(const long long start, const long long end): start(start), end(end) {
  }
};

class PraSolver {
  long long n{};
  long long m{};
  long long s{};
  std::vector<Range> ranges;
  long long schoolRangeIndex{};

public:
  PraSolver() {
    std::cin >> n >> m >> s;
    ranges.reserve(m);
    long start;
    long end;
    for(long long i = 0; i < m; i++) {
      std::cin >> start >> end;
      ranges.emplace_back(start, end);
    }
    if(getIndexOfRangeWithSchool() == -1) {
      ranges.emplace_back(s, s);
    }
    sortRanges();
    schoolRangeIndex = getIndexOfRangeWithSchool();
  }

  long long solve() const {
    long right = findFreeBuildingRight();
    long left = findFreeBuildingLeft();
    if(left == -1) {
      return right;
    }
    if(right == -1) {
      return left;
    }
    if(right - s < s - left) {
      return right;
    }
    return left;
  }

private:
  long long findFreeBuildingRight() const {
    for(long long i = schoolRangeIndex; i < ranges.size(); i++) {
      if(i + 1 == ranges.size()) {
        if(ranges[i].end == n) {
          return -1;
        }
        return ranges[i].end + 1;
      }
      if(ranges[i + 1].start != ranges[i].end + 1) {
        return ranges[i].end + 1;
      }
    }
    return -1;
  }

  long long findFreeBuildingLeft() const {
    for(long long i = schoolRangeIndex; i >= 0; i--) {
      if(i == 0) {
        if(ranges[i].start == 1) {
          return -1;
        }
        return ranges[i].start - 1;
      }
      if(ranges[i - 1].end != ranges[i].start - 1) {
        return ranges[i].start - 1;
      }
    }
    return -1;
  }

  void sortRanges() {
    std::qsort(ranges.data(), ranges.size(), sizeof(decltype(ranges)::value_type),
     [](const void* x, const void* y)
     {
       const auto* arg1 = static_cast<const Range*>(x);
       const auto* arg2 = static_cast<const Range*>(y);
       const auto cmp = arg1->start - arg2->start;
       if (cmp < 0)
         return -1;
       if (cmp > 0)
         return 1;
       return 0;
     });
  }

  long long getIndexOfRangeWithSchool() const {
    for(long long i = 0; i < ranges.size(); i++) {
      if(s <= ranges[i].end && ranges[i].start <= s) {
        return i;
      }
    }
    return -1;
  }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  PraSolver solver;
  long long result = solver.solve();
  std::cout << result;
  return 0;
}