class Node:
    def __init__(self,x,Next, Prev):
        self.data = x
        self.next = Next
        self.prev = Prev

class LinkedList:
    def __init__(self, *x):
        self.start = None
        self.last = None
        self.lenght = 0
        if x:
            for i in x:
                self.add(i)
        
    def __str__(self):
        if self.start != None:
            current = self.start
            out = '[ ' + str(current.data)
            while current.next != None:
                current = current.next
                out += ' '+ str(current.data)
            out += ' ]'
            return out
        
    def clear(self):
        self.__init__()
        
    def add(self, x):
        if self.start == None:
            self.start = self.last = Node(x,None,None)
            self.lenght += 1
        else:
            prev = self.last
            self.last.next = self.last = Node(x,None,None)
            self.last.prev = prev
            self.lenght += 1
            
    def addFew(self,*x):
        if x:
            for i in x:
                self.add(i)
            
            
    def remove(self, x,remove_all = False):
        current = self.start
        
        for i in range(self.lenght):
            if current.data == x:
                if current.prev == None:
                    if current.next != None:
                        self.start = current.next
                        current.next.prev = None
                        self.lenght -= 1
                        
                if current.next == None:
                    if current.prev != None:
                        current.prev.next = None
                        self.last = current.prev
                        self.last.next = None
                        self.lenght -= 1
                        
                if current.prev != None and current.next != None:
                    current.prev.next = current.next
                    current.next.prev = current.prev
                    self.lenght -= 1
                
                if current.next == None and current.prev == None:
                    clear(self)
                    self.lenght -= 0
                if remove_all == False:
                    break
            current = current.next

def binary_search(lst,item):
    low = 0
    high = len(lst) - 1
    while low <= high:
        mid = int((high + low)/2)
        guess = lst[mid]
        print (guess,mid)
        if guess > item:
            high = mid - 1
        if guess < item:
            low = mid + 1
        if guess == item:
            return mid
    else:
        return None