# -*- coding: utf-8 -*-
import csv
import time
import sys
import random
tinitial = time.time()
f = open('out_23_8_3.txt', 'a')
print ("",end="",file=f)
f.close()
tinitial = time.time()
i=0
j=0
def partition(list, start, end):
        pivot = list[end]
        bottom = start-1
        top = end
        done = 0
        while not done:
            while not done:
                bottom = bottom+1

                if bottom == top:
                    done = 1
                    break

                if list[bottom] > pivot:
                    list[top] = list[bottom]
                    break

            while not done:
                top = top-1                        # ... move the top down.
                if top == bottom:
                    done = 1
                    break

                if list[top] < pivot:
                    list[bottom] = list[top]
                    break

        list[top] = pivot                          # Put the pivot in its place.
        return top                                 # Return the split point

def quicksort(list, start, end):
        if start < end:
            split = partition(list, start, end)
            quicksort(list, start, split-1)
            quicksort(list, split+1, end)
        else:
            return

def binarySearch(arr, searchValue, left, right):
                if right < left:
                        return -1

                mid = int((left + right) / 2)
                if searchValue > arr[mid]:
                        return binarySearch(arr, searchValue, mid + 1, right)
                elif searchValue < arr[mid]:
                        return binarySearch(arr, searchValue, left, mid - 1)
                else:
                        return mid
#def deleten(arr,i)

infile= open('in8_3.txt',"r")
# Read in the data
csv_reader = csv.reader(infile)
f = open('out_23_8_3.txt', 'w')
for row in csv_reader:
    a=int(row[0])
    print (a)
    n=[]
    print ("n=",end="",file=f)
    for i in range(a):
#        print (i)
        n.append(random.randint(900,999))
    print (n,file=f)
    m=[]
    print("")
    b=int(row[1])
    print(" ",file=f)
    print ("m=",end="",file=f)
    m=random.sample(n,b)
    print (m,file=f)
    start = 0
    end = len(n)-1
    quicksort(n,start,end)
    print(n)
    endm=len(m)-1
    quicksort(m,start,endm)
    print(m)
    shift=0
    i=0
    r=0
    while (i<=b-1):
        k=binarySearch(n, m[endm-i], start, end)
        shift=shift+len(n)-k-1
        while (int(k)!=-1):
            n.remove(n[k])
            end=len(n)-1
            k=binarySearch(n, m[endm-i], start, end)
        while((m[endm-i]==m[endm-i-1]) and (endm-i-1>=0)):
            i=i+1
        i=i+1
print ("n=",n,file=f)
print (" ",file=f)
print ("Execution Time : ",(time.time()-tinitial)," Seconds",file=f)
print ("Shift : ",shift,file=f)
print ("Memory Used: ",sys.getsizeof(int)*((int(row[1])+int(row[0]))+3),file=f)
f.close()