#!/usr/bin/python
# -*- coding: utf-8 -*-
from collections import Counter
import random

def lomuto(seq):
    "My simplified version of Lomuto’s partitioning algorithm."
    i = 0
    for j in range(len(seq)):
        if seq[j] <= seq[-1]:
            seq[j], seq[i] = seq[i], seq[j]
            i += 1

    return i - 1

def test_lomuto(seq):
    original_counts = Counter(seq)
    original_last = seq[-1]
    p = lomuto(seq)
    assert original_counts == Counter(seq)
    assert seq[p] == original_last
    assert all(seq[i] <= seq[p] for i in range(p))
    assert all(seq[i] > seq[p] for i in range(p+1, len(seq)))

def test():
    test_lomuto([37])
    test_lomuto([37, 38])
    test_lomuto([37, 37])
    test_lomuto([3, 4, 5])
    test_lomuto([3, 5, 4])
    test_lomuto([4, 3, 5])
    test_lomuto([4, 5, 3])
    test_lomuto([5, 3, 4])
    test_lomuto([5, 4, 3])
    for ii in range(1000):
        test_lomuto([random.randrange(100) for ii in range(100)])

if __name__ == '__main__':
    import cgitb; cgitb.enable(format='text')
    test()