






"""simple docstring"""



from __future__ import annotations

_UpperCamelCase						:    Optional[int]		=						[2, 1, 4, 5, 6, 0, 8, 9, 1, 2, 0, 6, 4, 2, 0, 6, 5, 3, 2, 7]

class 			a	:







    def __init__(     self				,						_lowerCamelCase			):
      lowercase				       =			-1
      lowercase				       =			-1
      lowercase				       =			[-1] * length
      lowercase				       =			None
      lowercase				       =			None







    def __repr__(     self			):
      return F'Node(min_value={self.minn} max_value={self.maxx})'


def 		_SCREAMING_SNAKE_CASE					(       __snake_case     :    list[int]       ):





  '''simple docstring'''





  lowercase				       =			Node(len(__snake_case       )       )
  lowercase       ,	lowercase				       =			min(__snake_case       ), max(__snake_case       )
  # Leaf node case where the node contains only one unique value
  if root.minn == root.maxx:
    return root
  lowercase				       =			(root.minn + root.maxx) // 2

  lowercase				       =			[]
  lowercase				       =			[]

  for index, num in enumerate(__snake_case       ):
    if num <= pivot:
      left_arr.append(__snake_case       )
    else:
      right_arr.append(__snake_case       )
    lowercase				       =			len(__snake_case       )
  lowercase				       =			build_tree(__snake_case       )
  lowercase				       =			build_tree(__snake_case       )
  return root
def 		_SCREAMING_SNAKE_CASE					(       __snake_case     :    Node | None						,   __snake_case     :    int						,   __snake_case     :    int       ):





  '''simple docstring'''





  if index < 0 or node is None:
    return 0
  # Leaf node cases
  if node.minn == node.maxx:
    return index + 1 if node.minn == num else 0
  lowercase				       =			(node.minn + node.maxx) // 2
  if num <= pivot:
    # go the left subtree and map index to the left subtree
    return rank_till_index(node.left						,   __snake_case						,   node.map_left[index] - 1       )
  else:
    # go to the right subtree and map index to the right subtree
    return rank_till_index(node.right						,   __snake_case						,   index - node.map_left[index]       )
def 		_SCREAMING_SNAKE_CASE					(       __snake_case     :    Node | None						,   __snake_case     :    int						,   __snake_case     :    int						,   __snake_case     :    int       ):





  '''simple docstring'''





  if start > end:
    return 0
  lowercase				       =			rank_till_index(__snake_case						,   __snake_case						,   __snake_case       )
  lowercase				       =			rank_till_index(__snake_case						,   __snake_case						,   start - 1       )
  return rank_till_end - rank_before_start
def 		_SCREAMING_SNAKE_CASE					(       __snake_case     :    Node | None						,   __snake_case     :    int						,   __snake_case     :    int						,   __snake_case     :    int       ):





  '''simple docstring'''





  if index > (end - start) or start > end or node is None:
    return -1
  # Leaf node case
  if node.minn == node.maxx:
    return node.minn
  # Number of elements in the left subtree in interval [start, end]
  lowercase				       =			node.map_left[end] - (
      node.map_left[start - 1] if start else 0
  )
  if num_elements_in_left_tree > index:
    return quantile(
        node.left						,   __snake_case						,   (node.map_left[start - 1] if start else 0)						,   node.map_left[end] - 1						,   )
  else:
    return quantile(
        node.right						,   index - num_elements_in_left_tree						,   start - (node.map_left[start - 1] if start else 0)						,   end - node.map_left[end]						,   )
def 		_SCREAMING_SNAKE_CASE					(       __snake_case     :    Node | None						,   __snake_case     :    int						,   __snake_case     :    int						,   __snake_case     :    int						,   __snake_case     :    int       ):





  '''simple docstring'''





  if (
      start > end
      or node is None
      or start_num > end_num
      or node.minn > end_num
      or node.maxx < start_num
  ):
    return 0
  if start_num <= node.minn and node.maxx <= end_num:
    return end - start + 1
  lowercase				       =			range_counting(
      node.left						,   (node.map_left[start - 1] if start else 0)						,   node.map_left[end] - 1						,   __snake_case						,   __snake_case						,   )
  lowercase				       =			range_counting(
      node.right						,   start - (node.map_left[start - 1] if start else 0)						,   end - node.map_left[end]						,   __snake_case						,   __snake_case						,   )
  return left + right


if __name__ == "__main__":
    import doctest

    doctest.testmod()










"""simple docstring"""



import unittest

from transformers import ElectraConfig, is_torch_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, slow, torch_device

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
    import torch

    from transformers import (
        MODEL_FOR_PRETRAINING_MAPPING,
        ElectraForCausalLM,
        ElectraForMaskedLM,
        ElectraForMultipleChoice,
        ElectraForPreTraining,
        ElectraForQuestionAnswering,
        ElectraForSequenceClassification,
        ElectraForTokenClassification,
        ElectraModel,
    )
    from transformers.models.electra.modeling_electra import ELECTRA_PRETRAINED_MODEL_ARCHIVE_LIST

class 			a	:







    def __init__(     self				,						_lowerCamelCase				,						_lowerCamelCase=1_3				,						_lowerCamelCase=7				,						_lowerCamelCase=True				,						_lowerCamelCase=True				,						_lowerCamelCase=True				,						_lowerCamelCase=True				,						_lowerCamelCase=9_9				,						_lowerCamelCase=3_2				,						_lowerCamelCase=5				,						_lowerCamelCase=4				,						_lowerCamelCase=3_7				,						_lowerCamelCase="gelu"				,						_lowerCamelCase=0.1				,						_lowerCamelCase=0.1				,						_lowerCamelCase=5_1_2				,						_lowerCamelCase=1_6				,						_lowerCamelCase=2				,						_lowerCamelCase=0.0_2				,						_lowerCamelCase=3				,						_lowerCamelCase=4				,						_lowerCamelCase=None				,						):
      lowercase				       =			parent
      lowercase				       =			batch_size
      lowercase				       =			seq_length
      lowercase				       =			is_training
      lowercase				       =			use_input_mask
      lowercase				       =			use_token_type_ids
      lowercase				       =			use_labels
      lowercase				       =			vocab_size
      lowercase				       =			hidden_size
      lowercase				       =			num_hidden_layers
      lowercase				       =			num_attention_heads
      lowercase				       =			intermediate_size
      lowercase				       =			hidden_act
      lowercase				       =			hidden_dropout_prob
      lowercase				       =			attention_probs_dropout_prob
      lowercase				       =			max_position_embeddings
      lowercase				       =			type_vocab_size
      lowercase				       =			type_sequence_label_size
      lowercase				       =			initializer_range
      lowercase				       =			num_labels
      lowercase				       =			num_choices
      lowercase				       =			scope







    def      UpperCamelCase_ (     self			):
      lowercase				       =			ids_tensor([self.batch_size, self.seq_length]				,						self.vocab_size			)

      lowercase				       =			None
      if self.use_input_mask:
        lowercase				       =			random_attention_mask([self.batch_size, self.seq_length]			)

      lowercase				       =			None
      if self.use_token_type_ids:
        lowercase				       =			ids_tensor([self.batch_size, self.seq_length]				,						self.type_vocab_size			)

      lowercase				       =			None
      lowercase				       =			None
      lowercase				       =			None
      if self.use_labels:
        lowercase				       =			ids_tensor([self.batch_size]				,						self.type_sequence_label_size			)
        lowercase				       =			ids_tensor([self.batch_size, self.seq_length]				,						self.num_labels			)
        lowercase				       =			ids_tensor([self.batch_size]				,						self.num_choices			)
        lowercase				       =			ids_tensor([self.batch_size, self.seq_length]				,						1			)

      lowercase				       =			self.get_config()

      return (
          config,
          input_ids,
          token_type_ids,
          input_mask,
          sequence_labels,
          token_labels,
          choice_labels,
          fake_token_labels,
      )







    def      UpperCamelCase_ (     self			):
      return ElectraConfig(
          vocab_size=self.vocab_size				,						hidden_size=self.hidden_size				,						num_hidden_layers=self.num_hidden_layers				,						num_attention_heads=self.num_attention_heads				,						intermediate_size=self.intermediate_size				,						hidden_act=self.hidden_act				,						hidden_dropout_prob=self.hidden_dropout_prob				,						attention_probs_dropout_prob=self.attention_probs_dropout_prob				,						max_position_embeddings=self.max_position_embeddings				,						type_vocab_size=self.type_vocab_size				,						is_decoder=_lowerCamelCase				,						initializer_range=self.initializer_range				,						)







    def      UpperCamelCase_ (     self			):
      (
          (
          lowercase
      )       ,	(
          lowercase
      )       ,	(
          lowercase
      )       ,	(
          lowercase
      )       ,	(
          lowercase
      )       ,	(
          lowercase
      )       ,	(
          lowercase
      )       ,	(
          lowercase
      )       ,	
      )				       =			self.prepare_config_and_inputs()

      lowercase				       =			True
      lowercase				       =			floats_tensor([self.batch_size, self.seq_length, self.hidden_size]			)
      lowercase				       =			ids_tensor([self.batch_size, self.seq_length]				,						vocab_size=2			)

      return (
          config,
          input_ids,
          token_type_ids,
          input_mask,
          sequence_labels,
          token_labels,
          choice_labels,
          encoder_hidden_states,
          encoder_attention_mask,
      )







    def      UpperCamelCase_ (     self				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						):
      lowercase				       =			ElectraModel(config=_lowerCamelCase			)
      model.to(_lowerCamelCase			)
      model.eval()
      lowercase				       =			model(_lowerCamelCase				,						attention_mask=_lowerCamelCase				,						token_type_ids=_lowerCamelCase			)
      lowercase				       =			model(_lowerCamelCase				,						token_type_ids=_lowerCamelCase			)
      lowercase				       =			model(_lowerCamelCase			)
      self.parent.assertEqual(result.last_hidden_state.shape				,						(self.batch_size, self.seq_length, self.hidden_size)			)







    def      UpperCamelCase_ (     self				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						):
      lowercase				       =			True
      lowercase				       =			ElectraModel(_lowerCamelCase			)
      model.to(_lowerCamelCase			)
      model.eval()
      lowercase				       =			model(
          _lowerCamelCase				,						attention_mask=_lowerCamelCase				,						token_type_ids=_lowerCamelCase				,						encoder_hidden_states=_lowerCamelCase				,						encoder_attention_mask=_lowerCamelCase				,						)
      lowercase				       =			model(
          _lowerCamelCase				,						attention_mask=_lowerCamelCase				,						token_type_ids=_lowerCamelCase				,						encoder_hidden_states=_lowerCamelCase				,						)
      lowercase				       =			model(_lowerCamelCase				,						attention_mask=_lowerCamelCase				,						token_type_ids=_lowerCamelCase			)
      self.parent.assertEqual(result.last_hidden_state.shape				,						(self.batch_size, self.seq_length, self.hidden_size)			)







    def      UpperCamelCase_ (     self				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						):
      lowercase				       =			ElectraForMaskedLM(config=_lowerCamelCase			)
      model.to(_lowerCamelCase			)
      model.eval()
      lowercase				       =			model(_lowerCamelCase				,						attention_mask=_lowerCamelCase				,						token_type_ids=_lowerCamelCase				,						labels=_lowerCamelCase			)
      self.parent.assertEqual(result.logits.shape				,						(self.batch_size, self.seq_length, self.vocab_size)			)







    def      UpperCamelCase_ (     self				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						):
      lowercase				       =			ElectraForCausalLM(config=_lowerCamelCase			)
      model.to(_lowerCamelCase			)
      model.eval()
      lowercase				       =			model(_lowerCamelCase				,						attention_mask=_lowerCamelCase				,						token_type_ids=_lowerCamelCase				,						labels=_lowerCamelCase			)
      self.parent.assertEqual(result.logits.shape				,						(self.batch_size, self.seq_length, self.vocab_size)			)







    def      UpperCamelCase_ (     self				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						):
      lowercase				       =			self.num_labels
      lowercase				       =			ElectraForTokenClassification(config=_lowerCamelCase			)
      model.to(_lowerCamelCase			)
      model.eval()
      lowercase				       =			model(_lowerCamelCase				,						attention_mask=_lowerCamelCase				,						token_type_ids=_lowerCamelCase				,						labels=_lowerCamelCase			)
      self.parent.assertEqual(result.logits.shape				,						(self.batch_size, self.seq_length, self.num_labels)			)







    def      UpperCamelCase_ (     self				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						):
      lowercase				       =			self.num_labels
      lowercase				       =			ElectraForPreTraining(config=_lowerCamelCase			)
      model.to(_lowerCamelCase			)
      model.eval()
      lowercase				       =			model(_lowerCamelCase				,						attention_mask=_lowerCamelCase				,						token_type_ids=_lowerCamelCase				,						labels=_lowerCamelCase			)
      self.parent.assertEqual(result.logits.shape				,						(self.batch_size, self.seq_length)			)







    def      UpperCamelCase_ (     self				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						):
      lowercase				       =			self.num_labels
      lowercase				       =			ElectraForSequenceClassification(_lowerCamelCase			)
      model.to(_lowerCamelCase			)
      model.eval()
      lowercase				       =			model(_lowerCamelCase				,						attention_mask=_lowerCamelCase				,						token_type_ids=_lowerCamelCase				,						labels=_lowerCamelCase			)
      self.parent.assertEqual(result.logits.shape				,						(self.batch_size, self.num_labels)			)







    def      UpperCamelCase_ (     self				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						):
      lowercase				       =			ElectraForQuestionAnswering(config=_lowerCamelCase			)
      model.to(_lowerCamelCase			)
      model.eval()
      lowercase				       =			model(
          _lowerCamelCase				,						attention_mask=_lowerCamelCase				,						token_type_ids=_lowerCamelCase				,						start_positions=_lowerCamelCase				,						end_positions=_lowerCamelCase				,						)
      self.parent.assertEqual(result.start_logits.shape				,						(self.batch_size, self.seq_length)			)
      self.parent.assertEqual(result.end_logits.shape				,						(self.batch_size, self.seq_length)			)







    def      UpperCamelCase_ (     self				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase				,						):
      lowercase				       =			self.num_choices
      lowercase				       =			ElectraForMultipleChoice(config=_lowerCamelCase			)
      model.to(_lowerCamelCase			)
      model.eval()
      lowercase				       =			input_ids.unsqueeze(1			).expand(-1				,						self.num_choices				,						-1			).contiguous()
      lowercase				       =			token_type_ids.unsqueeze(1			).expand(-1				,						self.num_choices				,						-1			).contiguous()
      lowercase				       =			input_mask.unsqueeze(1			).expand(-1				,						self.num_choices				,						-1			).contiguous()
      lowercase				       =			model(
          _lowerCamelCase				,						attention_mask=_lowerCamelCase				,						token_type_ids=_lowerCamelCase				,						labels=_lowerCamelCase				,						)
      self.parent.assertEqual(result.logits.shape				,						(self.batch_size, self.num_choices)			)







    def      UpperCamelCase_ (     self			):
      lowercase				       =			self.prepare_config_and_inputs()
      (
          (
          lowercase
      )       ,	(
          lowercase
      )       ,	(
          lowercase
      )       ,	(
          lowercase
      )       ,	(
          lowercase
      )       ,	(
          lowercase
      )       ,	(
          lowercase
      )       ,	(
          lowercase
      )       ,	
      )				       =			config_and_inputs
      lowercase				       =			{'input_ids': input_ids, 'token_type_ids': token_type_ids, 'attention_mask': input_mask}
      return config, inputs_dict


@require_torch
class 			a	(  a_,							a_,							unittest.TestCase      ):
    UpperCAmelCase_					:	List[str]      	=(
        (
            ElectraModel,
            ElectraForPreTraining,
            ElectraForMaskedLM,
            ElectraForCausalLM,
            ElectraForMultipleChoice,
            ElectraForTokenClassification,
            ElectraForSequenceClassification,
            ElectraForQuestionAnswering,
        )
        if is_torch_available()
        else ()
    )
    UpperCAmelCase_					:	Optional[Any]      	=(
        {
            "feature-extraction": ElectraModel,
            "fill-mask": ElectraForMaskedLM,
            "question-answering": ElectraForQuestionAnswering,
            "text-classification": ElectraForSequenceClassification,
            "text-generation": ElectraForCausalLM,
            "token-classification": ElectraForTokenClassification,
            "zero-shot": ElectraForSequenceClassification,
        }
        if is_torch_available()
        else {}
    )
    UpperCAmelCase_					:	Tuple      	=True







    def      UpperCamelCase_ (     self				,						_lowerCamelCase				,						_lowerCamelCase				,						_lowerCamelCase=False			):
      lowercase				       =			super()._prepare_for_class(_lowerCamelCase				,						_lowerCamelCase				,						return_labels=_lowerCamelCase			)

      if return_labels:
        if model_class in get_values(_lowerCamelCase			):
          lowercase				       =			torch.zeros(
              (self.model_tester.batch_size, self.model_tester.seq_length)				,						dtype=torch.long				,						device=_lowerCamelCase			)
      return inputs_dict







    def      UpperCamelCase_ (     self			):
      lowercase				       =			ElectraModelTester(self			)
      lowercase				       =			ConfigTester(self				,						config_class=_lowerCamelCase				,						hidden_size=3_7			)







    def      UpperCamelCase_ (     self			):
      self.config_tester.run_common_tests()







    def      UpperCamelCase_ (     self			):
      lowercase				       =			self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_electra_model(*_lowerCamelCase			)







    def      UpperCamelCase_ (     self			):
      lowercase				       =			self.model_tester.prepare_config_and_inputs_for_decoder()
      self.model_tester.create_and_check_electra_model_as_decoder(*_lowerCamelCase			)







    def      UpperCamelCase_ (     self			):
      lowercase				       =			self.model_tester.prepare_config_and_inputs()
      for type in ["absolute", "relative_key", "relative_key_query"]:
        lowercase				       =			type
        self.model_tester.create_and_check_electra_model(*_lowerCamelCase			)







    def      UpperCamelCase_ (     self			):
      lowercase				       =			self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_electra_for_masked_lm(*_lowerCamelCase			)







    def      UpperCamelCase_ (     self			):
      lowercase				       =			self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_electra_for_token_classification(*_lowerCamelCase			)







    def      UpperCamelCase_ (     self			):
      lowercase				       =			self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_electra_for_pretraining(*_lowerCamelCase			)







    def      UpperCamelCase_ (     self			):
      lowercase				       =			self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_electra_for_sequence_classification(*_lowerCamelCase			)







    def      UpperCamelCase_ (     self			):
      lowercase				       =			self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_electra_for_question_answering(*_lowerCamelCase			)







    def      UpperCamelCase_ (     self			):
      lowercase				       =			self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_electra_for_multiple_choice(*_lowerCamelCase			)







    @slow
    def      UpperCamelCase_ (     self			):
      for model_name in ELECTRA_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
        lowercase				       =			ElectraModel.from_pretrained(_lowerCamelCase			)
        self.assertIsNotNone(_lowerCamelCase			)







    def      UpperCamelCase_ (     self			):
      lowercase				       =			self.model_tester.prepare_config_and_inputs_for_decoder()
      self.model_tester.create_and_check_electra_for_causal_lm(*_lowerCamelCase			)


@require_torch
class 			a	(  unittest.TestCase      ):







    @slow
    def      UpperCamelCase_ (     self			):
      lowercase				       =			ElectraModel.from_pretrained('google/electra-small-discriminator'			)
      lowercase				       =			torch.tensor([[0, 3_4_5, 2_3_2, 3_2_8, 7_4_0, 1_4_0, 1_6_9_5, 6_9, 6_0_7_8, 1_5_8_8, 2]]			)
      lowercase				       =			torch.tensor([[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]			)
      lowercase				       =			model(_lowerCamelCase				,						attention_mask=_lowerCamelCase			)[0]
      lowercase				       =			torch.Size((1, 1_1, 2_5_6)			)
      self.assertEqual(output.shape				,						_lowerCamelCase			)
      lowercase				       =			torch.tensor(
          [[[0.4_4_7_1, 0.6_8_2_1, -0.3_2_6_5], [0.4_6_2_7, 0.5_2_5_5, -0.3_6_6_8], [0.4_5_3_2, 0.3_3_1_3, -0.4_3_4_4]]]			)

      self.assertTrue(torch.allclose(output[:, 1:4, 1:4]				,						_lowerCamelCase				,						atol=1e-4			)			)


