Walmart came in our college for hiring and there was only one coding problem in the first round which took place on Hackerearth. I wasn't able to sove the question, but I am really curious about how to solve this question. So, here goes the question:

TIME LIMIT PER TEXT CASE: 1 sec. You are given a 1-indexed array A with N integers. Find the index i such that 1 < i < N and difference between the number of integers greater than A[i] in the range 1 to i-1 and the number of integers lesser than A[i] in the range i+1 to N is maximum.

INPUT: First line contains a number N as input. Next line contains N space seperated integers.

OUTPUT: In the output you need to print the maximum absolute difference that is obtained.

CONSTRAINT: 3 <= N <= 10^5; 1 <= A[i] <= 10^9

SAMPLE INPUT 1: 4 1 4 2 7

SAMPLE OUTPUT 1: 1

EXPLANATION: If we choose value 2 i.e. the index 3 then total elements greater than 2 to its left side is 1 and total elements lesser than 2 to es nget e 0 so the difference is 1 which is the maximum in the array.

NOTE: I have written the exact question which was provided to us.