What is the time complexity for Miller Rabin Primality Test?

Here is the algorithm from wikipedia page.

write n − 1 as 2^r·d where d is odd.

WitnessLoop: repeat k times: //runs k times.

{ pick a random integer a in the range [2, n − 1]

x ← a^d mod n

if x = 1 or x = n − 1 then

      continue WitnessLoop

 repeat r − 1 times:               //r=O(logn)

 {

      x ← x^2 mod n               //TC=O(logn)

      if x = 1 then

        return composite

      if x = n − 1 then

        continue WitnessLoop

 }

return composite

}

return probably prime

According to me the worst case time complexity would be O(k*(logn)^2)? But the wikipedia page mentions it as

O(k*(logn)^3). Can anyone help me out?

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

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?

What is the time complexity for building a segment tree for an array of size n?