Since I couldn’t solve the problem myself, I read up the concept and codes and managed to get it submitted via a Divide and Conquer (divide from middle) approach and a stack based O(n) solution. I also came up with a segment tree solution but it seems to be giving me a wrong answer. I’ve referred to different segment tree solutions but can’t seem to fix mine. Can anyone check out my approach and tell me what’s wrong here? (It gives me correct answer on the test cases provided)

Thanks!