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

Here's how I solved it in python.

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