Given an array of positive integers, replace every element with the least greater element to its right.
 If there is no greater element to its right, replace it with -1. For instance, given the array 
 
 `[8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28]`,
 
 the desired output is 
 
 `[18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1]`.

Your task is to create a function "arrayManip()" that takes in an array as its argument, manipulates the array as described above, then return the resulting array.

Note: Return a new array, rather than modifying the passed array.

Difficulty: introductory

Starter code:

def array_manip(array):
	

Solutions:
def array_manip(array):
    return [min([a for a in array[i+1:] if a > array[i]], default=-1) for i in range(len(array))]

def array_manip(array):
    return [min((r for r in array[i:] if r > n), default=-1) for i, n in enumerate(array, 1)]


# This is O(n²), it's a bad solution
# You can do it in O(n*log(n)) but I'm too lazy for now
def array_manip(array):
    return [min(filter(lambda y: y > x, array[i+1:]), default=-1) for i,x in enumerate(array)]

def array_manip(array):
    return [min((j for j in array[i+1:] if j > array[i]), default=-1) for i in range(len(array))]

def array_manip(array):
    return [
        min((x for x in array[i:] if x > n), default=-1)
        for i, n in enumerate(array)]

def array_manip(array):
    res = []
    for i, n in enumerate(array):
        try:
            res.append(min([x for x in array[i+1:] if x > n]))
        except ValueError:
            res.append(-1)
    return res

array_manip=lambda a:[min([m for m in a[i+1:]if m>n]or[-1])for i,n in enumerate(a)]

def array_manip(array):
    result = []
    for i in range(len(array)):
        try:
            cr = array[i]
            mm = sorted(x for x in array[i+1:] if x > cr)[0]
            result.append(mm)
        except:
            result.append(-1)
    return result

def array_manip(array):
    return [min(filter(lambda a: a > array[i], array[i+1:]), default=-1) for i in range(len(array))]

class BinaryTree:
    def __init__(self, value, left=None, right=None, parent=None):
        self.value = value
        self.left = left
        self.right = right
        self.parent = parent
        
    def __str__(self):
        if self.left or self.right:
            s = "(" + str(self.value)
            sl = self.left or '#'
            sr = self.right or '#'
            for l in str(sl).split("\n"):
                s += "\n  " + l
            for l in str(sr).split("\n"):
                s += "\n  " + l
            return s + ")"
        else:
            return f"{self.value}"

    def add(self, val):
        if val < self.value:
            if self.left:
                return self.left.add(val)
            else:
                self.left = BinaryTree(val, parent=self)
                return self.left
        elif val > self.value:
            if self.right:
                return self.right.add(val)
            else:
                self.right = BinaryTree(val, parent=self)
                return self.right
        elif val == self.value:
            return self
    
    def leftmost(self):
        x = self
        while x.left:
            x = x.left
        return x

    def nxt(self):
        if self.right:
            return self.right.leftmost().value
        else:
            x = self.parent
            while x and x.value < self.value:
                x = x.parent
            if x:
                return x.value
            
        return -1

def array_manip(array):
    if not array:
        return []
    
    result = []
    b = BinaryTree(array[-1])
    
    for item in reversed(array):
        result.append(b.add(item).nxt())
        
    return result[::-1]