class Solution {
public:
  vector<string> findMissingRanges(const vector<int>& nums, int lower,
                                   int upper) {
    vector<string> res;
    if (nums.empty()) {
      res.push_back(append_range(lower, upper));
      return res;
    }
    int64_t first = nums[0];
    if (first != lower) {
      res.push_back(append_range(lower, first - 1));
    }
    int64_t prev = first;
    for (int i = 1; i < nums.size(); i++) {
      int64_t cur = nums[i];
      if (cur - prev > 1) {
        res.push_back(append_range(prev + 1, cur - 1));
      }
      prev = nums[i];
    }

    int64_t last = nums[nums.size() - 1];
    if (last != upper) {
      res.push_back(append_range(last + 1, upper));
    }
    return res;
  }

private:
  string append_range(int64_t b, int64_t e) {
    if (b == e) {
      return to_string(b);
    } else {
      string res;
      res.append(to_string(b));
      res.append("->");
      res.append(to_string(e));
      return res;
    }
  }
};