





def _a       (			lowerCamelCase:     str				)			->		int:







						'''simple docstring'''






						__A      =       53_81
						for x in s:
												__A      =       ((hash_value << 5) + hash_value) + ord(lowerCamelCase				)
						return hash_value & 0Xf_f_f_f_f_f_f_f












class A_      :




   def __init__(self			:Union[str, Any]				)->      None:
         # numbermap keys are the number and its values are lists of indexes sorted
         # in ascending order
         __A      =       {}
         # indexmap keys are an index and it's values are the number at that index
         __A      =       {}




   def _lowerCAmelCase   (self			:Any					,     _UpperCamelCase			:list | str | range					,     _UpperCamelCase			:int				)->      list[int]:
         if isinstance(_UpperCamelCase					,     (range, str)				):
               __A      =       list(_UpperCamelCase				)
         elif not isinstance(_UpperCamelCase					,     _UpperCamelCase				):
               raise TypeError(
                   '''binary_search_delete() only accepts either a list, range or str'''				)

         __A      =       0
         __A      =       len(_UpperCamelCase				) - 1

         while low <= high:
               __A      =       (low + high) // 2
               if array[mid] == item:
                     array.pop(_UpperCamelCase				)
                     return array
               elif array[mid] < item:
                     __A      =       mid + 1
               else:
                     __A      =       mid - 1
         raise ValueError(
             '''Either the item is not in the array or the array was unsorted'''				)




   def _lowerCAmelCase   (self			:Optional[Any]					,     _UpperCamelCase			:list | str | range					,     _UpperCamelCase			:int				)->      list[int]:
         if isinstance(_UpperCamelCase					,     (range, str)				):
               __A      =       list(_UpperCamelCase				)
         elif not isinstance(_UpperCamelCase					,     _UpperCamelCase				):
               raise TypeError(
                   '''binary_search_insert() only accepts either a list, range or str'''				)

         __A      =       0
         __A      =       len(_UpperCamelCase				) - 1

         while low <= high:
               __A      =       (low + high) // 2
               if array[mid] == index:
                     # If the item already exists in the array,
                     # insert it after the existing item
                     array.insert(mid + 1					,     _UpperCamelCase				)
                     return array
               elif array[mid] < index:
                     __A      =       mid + 1
               else:
                     __A      =       mid - 1

        # If the item doesn't exist in the array, insert it at the appropriate position
         array.insert(_UpperCamelCase					,     _UpperCamelCase				)
         return array




   def _lowerCAmelCase   (self			:Union[str, Any]					,     _UpperCamelCase			:int					,     _UpperCamelCase			:int				)->      None:
         # Remove previous index
         if index in self.indexmap:
               __A      =       self.indexmap[index]
               if len(self.numbermap[n]				) == 1:
                     del self.numbermap[n]
               else:
                     __A      =       self.binary_search_delete(self.numbermap[n]					,     _UpperCamelCase				)

        # Set new index
         __A      =       number

         # Number not seen before or empty so insert number value
         if number not in self.numbermap:
               __A      =       [index]

         # Here we need to perform a binary search insertion in order to insert
         # The item in the correct place
         else:
               __A      =       self.binary_search_insert(
                   self.numbermap[number]					,     _UpperCamelCase				)






   def _lowerCAmelCase   (self			:List[Any]					,     _UpperCamelCase			:int				)->      int:
         return self.numbermap.get(_UpperCamelCase					,     [-1]				)[0]


if __name__ == "__main__":
       import doctest

       doctest.testmod()





