Constraints:

Size of the array: [1 10^5]

Element: 1 <= a[i] <= 10^6

Brute force won't work because of the constraints. I tried thinking of various ways but all were convoluted. I feel there is an easier way to think about it but I am missing some observation.

Any help would be highly appreciated.

Thanks!