as constraints given in the problem wants linear solution or nlogn solution for the problem

but the lot of people submitted O(n^2) solution and get AC

there should be strong test cases

https://www.codechef.com/ROCS2021/problems/ROCSAD

LOL , I think they forgot to add " sum of n over all test cases <=1000"

BTW It can be solved using lower_bound for the given constraints.

I also written solution using two loops

But i dont think so it was Quadratic in time

Because i optimized the inner loop in such way that i took absolute diff until it decreasing and stopped when absolute diff started increasing

So as per my observation inner loop will not take O(n)

time

So it got accepted .

Lets say we have

-5 -1 3 5 6

-4 -2 0 4 7

first

abs(-5-(-4)) = 1

then

abs(-5-(-2)) = 3

break ;

as 3 > 1 the abs diff started increasing i breaked inner loop

for -1

abs(-1-(-4)) = 3

abs(-1-(-2)) = 1

abs(-1-0) = 1

abs(-1-4) = 5

since 5 >1 break inner loop

Also another optimization is if once you got abs diff as 0 you need not to check for any next elements as 0 is least in abs difference .