Once you understand the logic. The question will look very easy.

Here's the solution in Python. Java,C++

Hackerrank - Array Manipulation Solution

My answer is O(m log m) and it is faster than O(n)

The maximum value of n is 10**7 whereas m log m is 5*10**5