Задача на сортировку

Информатика
1 
#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long n;
	cin>>n;
	vector <long long> vec;
	for(long long i=1;i<=n;i++)
	{
		vec.push_back(i*i);
		vec.push_back(i*i*i);
	}
	sort(vec.begin(),vec.end());
	int cnt=1;
	for(int i=0;i<(n*2);i++)
	{
		if(cnt==n)
		{
			cout<<vec[i];
			break;
		}
		if(vec[i]!=vec[i+1])
		{
			cnt++;
		}
	}
	return 0;
}

Написал код проходит 8 тестов из 10, по остальным тайм лимит, задача: Поиск и сортировка

2

Хотелось бы подсказку

3

В задаче нужно отсортировать их за O(N), std sort работает O(NlogN). Чтобы отсортировать в этой задаче тебе нужно посмотреть как сливаются в мердж сорте массивы