Ciężko jest mi podać wskazówkę dla Pythona - nie używam go na SPOJu.
Może spróbuj przedefiniować problem na taki, który można rozwiązać znanymi metodami? Np. może istnieje jakaś struktura danych, która została zaprojektowana celem wyznaczania czegoś o najwyższym ( 
) priorytecie? Może da się ją jakoś sprytnie wykorzystać?
Bo jeśli chodzi o wyznaczanie minimum na już utworzonej liście to ciężko o metodę inną niż O(n) polegającą na przyjęciu za element najmniejszy pierwszego elementu listy, a następnie zachłannym wybieraniu jako nowego minimum tego samego elementu albo kolejnego elementu z listy.
Ewentualnie można posortować i wybrać minimum w O(1), ale wtedy masz dodatkowy narzut na sortowanie, a tu ciężko zejść do O(1), a nawet O(n).
