Better explanation of algorithm


#1

Basically, algorithms maintains a value which is second greatest element(so called root) to left side of a[i](before iterating for i). As this is the best canditate for comparing and stack maintains a increasing(not strictly) sequence from top to bottom. It’s bottom element is greatest element found yet. so you are searching for an element which is smaller than second greatest. 2nd Greatest -> Greatest -> smaller than 2nd greatest.