def partition(A,p,q,loc):
    A[p],A[loc] = A[loc],A[p]
    i = p
    for j in range(p+1,q+1):
        if A[j] <= A[p]:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i], A[p] = A[p], A[i]
    return i