I am given an array A of size n. I have to answer q queries of the form [Li,Ri]

Answer to the query [Li,Ri] is the minimum of all A[x] for all x from [Li,Ri].

1≤n,q≤10^5 , 1≤Ai≤10^9

Segment Tree implementation of the input array gets us the complexity of O(n) for creating the segment tree and O(log(n)) for queries. Overall Complexity- O(n+qlog(n))

Complexity for creating cartesian tree is O(n) and then for range queries we need to find the LCA of the 2 indices and the complexity for that is O(log(n)) Overall Complexity-O(n+qlog(n))

The segment tree implementation is doing good. But I am getting Time Limit Exceeded in the Cartesian Tree Implementation. Can anyone explain me the reason behind this?