def huffman_len(arr):
    class tree_node:
        def __init__(self, freq=None, left=None, right=None):
            self.freq = freq
            self.left = left
            self.right = right

    class min_heap_tree:
        def heapify(self, root):
            left = 2 * root + 1
            right = 2 * root + 2
            lowest = root

            if left < self.heap_len and self.heap[left].freq < self.heap[lowest].freq:
                lowest = left

            if right < self.heap_len and self.heap[right].freq < self.heap[lowest].freq:
                lowest = right

            if lowest != root:
                self.heap[root], self.heap[lowest] = self.heap[lowest], self.heap[root]
                self.heapify(lowest)

        def build_heap(self):
            for i in range(self.heap_len // 2, -1, -1):
                self.heapify(i)

        def add_to_heap(self, node):
            self.heap[self.heap_len]=node
            self.heap_len+=1
            self.added_last(self.heap_len - 1)

        def added_last(self, child):
            if child == 0:
                return
            parent = (child - 1) // 2

            if self.heap[parent].freq > self.heap[child].freq:
                self.heap[child], self.heap[parent] = self.heap[parent], self.heap[child]
                self.added_last(parent)

        def get_min(self):
            res = self.heap[0]

            self.heap[0]=self.heap[self.heap_len-1]
            self.heap_len-=1
            self.heapify(0)
            return res

        def __init__(self, arr):
            self.heap = [None]*len(arr)
            self.heap_len = len(arr)

            for i in range(self.heap_len):
                tmp = tree_node(arr[i])
                self.heap[i]=tmp

            self.build_heap()

    class huffman_tree:
        def __init__(self):
            self.root = None
            self.arr=[]
            self.heap=[]

        def create_tree(self, arr):
            self.arr = arr
            self.heap = min_heap_tree(self.arr)
            parent=None

            while self.heap.heap_len > 1:
                left = self.heap.get_min()
                right = self.heap.get_min()

                parent = tree_node(left.freq + right.freq, left, right)

                self.heap.add_to_heap(parent)

            self.root = parent

        def get_code_len(self):
            def _get_code_len(root, i):
                if root is None:
                    return 0
                if root.right is None and root.left is None:
                    return i*root.freq
                return _get_code_len(root.left, i + 1)+_get_code_len(root.right,  i + 1)

            return _get_code_len(self.root, 0)

    tree=huffman_tree()
    tree.create_tree(arr)

    return tree.get_code_len()


print(huffman_len([200, 700, 180, 120, 70, 30]))