Looking for algorithm which solves the problem
in O(n).
Why don’t you look at the editorial which is already provided here?
thanks the link wasn’t there(with problem).