def dual_pivot_randomized_quicksort(arr):
    start_time=time.time()
    lo=0
    hi=len(arr)-1
    dual_quicksort(arr,lo,hi)
    return time.time()-start_time


def dual_quicksort(arr,lo,hi):
    if(lo<hi):
        p1,p2=dual_randomized_partition(arr,lo,hi)
        dual_quicksort(arr,lo,p1-1)
        dual_quicksort(arr,p1+1,p2-1)
        dual_quicksort(arr,p2+1,hi)

def dual_randomized_partition(arr,lo,hi):
    if(lo>=hi):
        return
    pivot1=random.randint(lo,hi)
    pivot2=random.randint(lo,hi)
    while(pivot1==pivot2):
        pivot1=random.randint(lo,hi)
    if(pivot1>pivot2):
        pivot1,pivot2=pivot2,pivot1

    pivot1_value=arr[pivot1]
    pivot2_value=arr[pivot2]

    if(pivot1_value>pivot2_value):
        arr[pivot1],arr[pivot2]=arr[pivot2],arr[pivot1]
        pivot1_value=arr[pivot1]
        pivot2_value=arr[pivot2]

    arr[pivot1],arr[lo]=arr[lo],arr[pivot1]
    arr[pivot2],arr[hi]=arr[hi],arr[pivot2]

    l=lo+1
    g=hi-1
    k=l
    p=arr[lo]
    q=arr[hi]

    if(p>q):
        arr[lo],arr[hi]=arr[hi],arr[lo]
        p=arr[lo]
        q=arr[hi]

    while(k<=g):
        if arr[k]< p:
            arr[k],arr[l]=arr[l],arr[k]
            l+=1
        elif(arr[k]>=q):
                while(arr[g] > q and k<g):
                    g-=1
                arr[k],arr[g]=arr[g],arr[k]
                g-=1
                if(arr[k]<p):
                    arr[k],arr[l]=arr[l],arr[k]
                    l+=1
        k+=1

    l-=1
    g+=1
    arr[l],arr[lo]=arr[lo],arr[l]
    arr[g],arr[hi]=arr[hi],arr[g]
    return (l,g)