# Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted
# order, not the kth distinct element.
#
# Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains
# initial elements from the stream. For each call to the method KthLargest.add, return the element representing the
# kth largest element in the stream.
#
# Example:
#
# int k = 3;
# int[] arr = [4,5,8,2];
# KthLargest kthLargest = new KthLargest(3, arr);
# kthLargest.add(3);   // returns 4
# kthLargest.add(5);   // returns 5
# kthLargest.add(10);  // returns 5
# kthLargest.add(9);   // returns 8
# kthLargest.add(4);   // returns 8
import heapq


class KthLargest(object):

    def __init__(self, k, nums):
        """
        :type k: int
        :type nums: List[int]
        """
        self._heap, self._k = [], k

        for n in nums:
            self.add(n)

    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
        if len(self._heap) < self._k:
            heapq.heappush(self._heap, val)
        else:
            if val > self._heap[0]:
                heapq.heappop(self._heap)
                heapq.heappush(self._heap, val)

        return self._heap[0]
