'''
keys: 
Solutions:
Similar:
T:
S:
'''
from typing import List

class CustomStack:
    def __init__(self, maxSize):
        self.n = maxSize
        self.stack = []
        self.inc = []
        
    # inc[i] means for all elements stack[0] ~ stack[i],
    # we should plus inc[i] when popped from the stack.
    # Then inc[i-1]+=inc[i],
    # so that we can accumulate the increment inc[i]
    # for the bottom elements and the following pops.
    def push(self, x):
        if len(self.inc) < self.n:
            self.stack.append(x)
            self.inc.append(0) # no increment

    def pop(self):
        if not self.inc: return -1
        if len(self.inc) > 1: 
            self.inc[-2] += self.inc[-1] # keep the increment
        return self.stack.pop() + self.inc.pop()

    def increment(self, k, val):
        if self.inc:
            self.inc[min(k, len(self.inc)) - 1] += val
            
            
            
        
# advanced version with peek, empty, and sum
class AddingStack:
    def __init__(self) -> None:
        self.stack = []
        self.increment = []
        self.sum_ = 0
    
    def push(self, v : int) -> None:
        # Complete the function below
        self.stack.append(v)
        self.increment.append(0)
        self.sum_ += v
    
    def pop(self) -> None:
        # Complete the function below
        if len(self.stack) == 0:
            return -1
        if len(self.increment) > 1:
            self.increment[-2] += self.increment[-1]
        self.sum_ -= (self.stack[-1] + self.increment[-1])
        return self.stack.pop() + self.increment.pop()
            
    
    def inc(self, i : int, v: int) -> None:
        # Complete the function below
        if not self.increment:
            return
        self.increment[min(i, len(self.stack)) - 1] += v
        self.sum_ += v * min(i, len(self.stack))
    
    def empty(self) -> bool:
        # Complete the function below
        if self.stack:
            return False
        else:
            return True
    
    def peek(self) -> int:
        # Complete the function below
        # l = len(self.stack)
        return self.stack[-1] + self.increment[-1]
    
    def sum(self) -> int:
        # Complete the function below
        return self.sum_
    