text: """703. Kth Largest Element in a Stream
  https://leetcode.com/problems/kth-largest-element-in-a-stream/
  
  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.
  
  Implement KthLargest class:
  
  KthLargest(int k, int[] nums) Initializes the object with the integer k and
  the stream of integers nums.
  int add(int val) Returns the element representing the kth largest element in
  the stream.
   
  
  Example 1:
  
  Input
  ["KthLargest", "add", "add", "add", "add", "add"]
  [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
  Output
  [null, 4, 5, 5, 8, 8]
  
  Explanation
  KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
  kthLargest.add(3);   // return 4
  kthLargest.add(5);   // return 5
  kthLargest.add(10);  // return 5
  kthLargest.add(9);   // return 8
  kthLargest.add(4);   // return 8
   
  
  Constraints:
  
  1 <= k <= 10^4
  0 <= nums.length <= 10^4
  -10^4 <= nums[i] <= 10^4
  -10^4 <= val <= 10^4
  At most 104 calls will be made to add.
  It is guaranteed that there will be at least k elements in the array when you
  search for the kth element.
  """
  from typing import List
  import bisect
  import heapq
  
  
  class KthLargest:
  
      def __init__(self, k: int, nums: List[int]):
          self.k = k
          self.nums = sorted(nums)
  
      def add(self, val: int) -> int:
          i = bisect.bisect(self.nums, val)
          self.nums.insert(i, val)
          return self.nums[len(self.nums) - self.k]
  
  
  class KthLargest2:
  
      def __init__(self, k: int, nums: List[int]):
          self.k = k
          self.pq = []
          heapq.heapify(self.pq)
          for num in nums:
              self.add(num)
  
      def add(self, val: int) -> int:
          heapq.heappush(self.pq, val)
          if len(self.pq) > self.k:
              heapq.heappop(self.pq)
          return self.pq[0]
  