#include <vector>
#include <algorithm>

struct Pair {
    int first;
    int second;

    Pair(int f, int s) : first(f), second(s) {}
    Pair() : first(0), second(0) {}
    bool operator>(const Pair& other) const {
        return first > other.first;
    }
    bool operator<(const Pair& other) const {
        return first < other.first;
    }
};

class TwoSumSolution {
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        std::vector<Pair> numPairs;
        int i = 0;
        for (auto num : nums) {
            numPairs.emplace_back(num, i);
            i++;
        }
        std::sort(numPairs.begin(), numPairs.end());
        while (true)
        {
            int left = 0;
            int right = static_cast<int>(numPairs.size()) - 1;
            while (left < right) {
                int sum = numPairs[left].first + numPairs[right].first;
                if (sum == target) {
                    return std::vector<int>{numPairs[left].second, numPairs[right].second};
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
            break;
        }

        return std::vector<int>{};
    }
};