/*Uses binary search for Log N complexity*/
int findClosestNumberIndex(int num, int start, int end, const std::vector<int>& v)
{
    const int pivot = (end + start) / 2;
    if(v.at(pivot) == num || start >= end)
    {
        return pivot;
    }
    if(num > v.at(pivot))
    {
        return findClosestNumberIndex(num, start, pivot - 1, v);
    }
    if(num < v.at(pivot))
    {
        return findClosestNumberIndex(num, pivot + 1, end, v);
    }
    return -1;
}

std::vector<int> climbingLeaderboard(std::vector<int> ranked, std::vector<int> player) 
{
		/*Map used for fast search access*/
    std::map<int, int> posScores {{ranked.at(0), 1}};
    int cl = 1;
    for(int i = 1; i < ranked.size(); ++i)
    {
        if(ranked.at(i) != ranked.at(i - 1))
        {
            ++cl;
            posScores.emplace(ranked.at(i), cl);
        }
    } 

    std::vector<int> result;
    result.reserve(player.size());
    for(const int playerScore : player)
    {
        int pos = -1;
				/*If the exact same value is found in the map, we don't need to find the closest number*/
        auto It = posScores.find(playerScore);
        if(It != posScores.end())
        {
            pos = It->second;
        }
        else
        {
            const int closestNumIndex = findClosestNumberIndex(playerScore, 0, ranked.size() - 1, ranked);
            const std::pair<int, int> pairFound = *posScores.find(ranked.at(closestNumIndex));
            pairFound.first > playerScore ? pos = pairFound.second + 1 : pos = pairFound.second;
        }

        result.push_back(pos);
    }

    return result;
}