

import math



class    A__:
						"""simple docstring"""






						def __init__(  self       ,     _lowercase  )      ->				List[str]:
									a_		:		Union[str, Any]				    =				len(UpperCamelCase__  )
									a_		:		Optional[Any]				    =				[0] * (
									    4 * self.N
									)  # approximate the overall size of segment tree with array N
									self.build(1       ,     0       ,     self.N - 1  )





						def 	UpperCamelCase__			(  self       ,     _lowercase  )      ->				Optional[int]:
									return idx * 2





						def 	UpperCamelCase__			(  self       ,     _lowercase  )      ->				List[str]:
									return idx * 2 + 1





						def 	UpperCamelCase__			(  self       ,     _lowercase       ,     _lowercase       ,     _lowercase  )      ->				str:  # noqa: E741






									if l == r:
												a_		:		Union[str, Any]				    =				A[l]
									else:
												a_		:		Tuple				    =				(l + r) // 2
												self.build(self.left(UpperCamelCase__  )       ,     UpperCamelCase__       ,     UpperCamelCase__  )
												self.build(self.right(UpperCamelCase__  )       ,     mid + 1       ,     UpperCamelCase__  )
												a_		:		Optional[int]				    =				max(self.st[self.left(UpperCamelCase__  )]       ,     self.st[self.right(UpperCamelCase__  )]  )





						def 	UpperCamelCase__			(  self       ,     _lowercase       ,     _lowercase       ,     _lowercase  )      ->				Any:
									return self.update_recursive(1       ,     0       ,     self.N - 1       ,     a - 1       ,     b - 1       ,     UpperCamelCase__  )





						def 	UpperCamelCase__			(  self       ,     _lowercase       ,     _lowercase       ,     _lowercase       ,     _lowercase       ,     _lowercase       ,     _lowercase  )      ->				str:  # noqa: E741






									if r < a or l > b:
												return True
									if l == r:
												a_		:		Optional[int]				    =				val
												return True
									a_		:		Dict				    =				(l + r) // 2
									self.update_recursive(self.left(UpperCamelCase__  )       ,     UpperCamelCase__       ,     UpperCamelCase__       ,     UpperCamelCase__       ,     UpperCamelCase__       ,     UpperCamelCase__  )
									self.update_recursive(self.right(UpperCamelCase__  )       ,     mid + 1       ,     UpperCamelCase__       ,     UpperCamelCase__       ,     UpperCamelCase__       ,     UpperCamelCase__  )
									a_		:		Dict				    =				max(self.st[self.left(UpperCamelCase__  )]       ,     self.st[self.right(UpperCamelCase__  )]  )
									return True





						def 	UpperCamelCase__			(  self       ,     _lowercase       ,     _lowercase  )      ->				Union[str, Any]:
									return self.query_recursive(1       ,     0       ,     self.N - 1       ,     a - 1       ,     b - 1  )





						def 	UpperCamelCase__			(  self       ,     _lowercase       ,     _lowercase       ,     _lowercase       ,     _lowercase       ,     _lowercase  )      ->				Any:  # noqa: E741






									if r < a or l > b:
												return -math.inf
									if l >= a and r <= b:
												return self.st[idx]
									a_		:		Union[str, Any]				    =				(l + r) // 2
									a_		:		int				    =				self.query_recursive(self.left(UpperCamelCase__  )       ,     UpperCamelCase__       ,     UpperCamelCase__       ,     UpperCamelCase__       ,     UpperCamelCase__  )
									a_		:		Union[str, Any]				    =				self.query_recursive(self.right(UpperCamelCase__  )       ,     mid + 1       ,     UpperCamelCase__       ,     UpperCamelCase__       ,     UpperCamelCase__  )
									return max(UpperCamelCase__       ,     UpperCamelCase__  )





						def 	UpperCamelCase__			(  self  )      ->				int:
									a_		:		Any				    =				[]
									for i in range(1       ,     N + 1  ):
												show_list += [self.query(UpperCamelCase__       ,     UpperCamelCase__  )]
									print(UpperCamelCase__  )


if __name__ == "__main__":
	__snake_case							:     int 						=	[1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
	__snake_case							:     Optional[Any] 						=	15
	__snake_case							:     Tuple 						=	SegmentTree(A)
	print(segt.query(4, 6))
	print(segt.query(7, 11))
	print(segt.query(7, 12))
	segt.update(1, 3, 1_11)
	print(segt.query(1, 15))
	segt.update(7, 8, 2_35)
	segt.show_data()





import unittest
from functools import partial

import torch

from accelerate import Accelerator, debug_launcher
from accelerate.state import AcceleratorState, GradientState
from accelerate.test_utils import require_cpu, require_huggingface_suite
from accelerate.utils import GradientAccumulationPlugin


def 			_UpperCAmelCase							(		a__=2       ,					a__=True       ,					a__=False):

			'''simple docstring'''



			a_		:		Optional[Any]				    =				Accelerator(step_scheduler_with_optimizer=a__       ,					split_batches=a__)
			a_		:		Dict				    =				torch.nn.Linear(2       ,					4)
			a_		:		int				    =				torch.optim.AdamW(model.parameters()       ,					lr=1.0)
			a_		:		Optional[int]				    =				torch.optim.lr_scheduler.OneCycleLR(a__       ,					max_lr=0.01       ,					steps_per_epoch=2       ,					epochs=1)
			a_    ,			a_    ,			a_		:		List[Any]				    =				accelerator.prepare(a__       ,					a__       ,					a__)

			# Optimizer has stepped
			scheduler.step()
			if step_scheduler_with_optimizer or (num_processes == 1):
						assert (
						    scheduler.scheduler.last_epoch == num_processes
						), f'''Last Epoch ({scheduler.scheduler.last_epoch}) != Num Processes ({num_processes})'''
			else:
						assert (
						    scheduler.scheduler.last_epoch != num_processes
						), f'''Last Epoch ({scheduler.scheduler.last_epoch}) == Num Processes ({num_processes})'''


def 			_UpperCAmelCase							(		a__=2       ,					a__=True       ,					a__=False):

			'''simple docstring'''



			a_		:		int				    =				Accelerator(step_scheduler_with_optimizer=a__       ,					split_batches=a__)
			a_		:		Tuple				    =				torch.nn.Linear(2       ,					4)
			a_		:		str				    =				torch.optim.AdamW(model.parameters()       ,					lr=1.0)
			a_		:		Optional[int]				    =				torch.optim.lr_scheduler.LambdaLR(a__       ,					lr_lambda=lambda a__: 1 - n / 1_0)
			a_    ,			a_    ,			a_		:		List[str]				    =				accelerator.prepare(a__       ,					a__       ,					a__)

			# Optimizer has stepped
			a_		:		Optional[Any]				    =				False
			scheduler.step()
			a_		:		Union[str, Any]				    =				1 - (num_processes if (step_scheduler_with_optimizer and not split_batches) else 1) / 1_0
			assert (
			    scheduler.get_last_lr()[0] == expected_lr
			), f'''Wrong lr found at first step, expected {expected_lr}, got {scheduler.get_last_lr()[0]}'''

			# Optimizer has not stepped
			a_		:		Any				    =				True
			scheduler.step()
			if not step_scheduler_with_optimizer:
						a_		:		Any				    =				1 - 2 / 1_0
			assert (
			    scheduler.get_last_lr()[0] == expected_lr
			), f'''Wrong lr found at second step, expected {expected_lr}, got {scheduler.get_last_lr()[0]}'''


def 			_UpperCAmelCase							(		a__ = 2):

			'''simple docstring'''



			from transformers import get_linear_schedule_with_warmup

			a_		:		int				    =				[1, 2, 4]
			for num_steps in steps:
						a_		:		List[str]				    =				GradientAccumulationPlugin(num_steps=a__       ,					adjust_scheduler=num_steps > 1)
						a_		:		List[str]				    =				Accelerator(gradient_accumulation_plugin=a__)
						a_		:		int				    =				torch.nn.Linear(2       ,					4)
						a_		:		Any				    =				torch.optim.AdamW(model.parameters()       ,					lr=10.0)
						a_		:		List[Any]				    =				get_linear_schedule_with_warmup(optimizer=a__       ,					num_warmup_steps=0       ,					num_training_steps=2_0)

						a_    ,			a_    ,			a_		:		int				    =				accelerator.prepare(a__       ,					a__       ,					a__)

						for i in range(1_0 * num_steps):
									with accelerator.accumulate(a__):
												optimizer.step()
												scheduler.step()

									if i == (1_0 * num_steps - 2):
												assert (
												    scheduler.get_last_lr()[0] != 0
												), f'''Wrong lr found at second-to-last step, expected non-zero, got {scheduler.get_last_lr()[0]}. num_steps: {num_steps}'''
						assert (
						    scheduler.get_last_lr()[0] == 0
						), f'''Wrong lr found at last step, expected 0, got {scheduler.get_last_lr()[0]}'''
						GradientState._reset_state()



@require_cpu
class    A__(unittest.TestCase    ):
						"""simple docstring"""






						def 	UpperCamelCase__			(  self  )      ->				str:
									debug_launcher(partial(_lowercase       ,     num_processes=1  )       ,     num_processes=1  )
									debug_launcher(partial(_lowercase       ,     num_processes=1       ,     split_batches=_lowercase  )       ,     num_processes=1  )





						def 	UpperCamelCase__			(  self  )      ->				Dict:
									debug_launcher(partial(_lowercase       ,     num_processes=1  )       ,     num_processes=1  )
									debug_launcher(partial(_lowercase       ,     num_processes=1       ,     split_batches=_lowercase  )       ,     num_processes=1  )





						def 	UpperCamelCase__			(  self  )      ->				Any:
									debug_launcher(partial(_lowercase       ,     num_processes=1       ,     step_scheduler_with_optimizer=_lowercase  )       ,     num_processes=1  )





						def 	UpperCamelCase__			(  self  )      ->				Tuple:
									debug_launcher(partial(_lowercase       ,     num_processes=1       ,     step_scheduler_with_optimizer=_lowercase  )       ,     num_processes=1  )





						def 	UpperCamelCase__			(  self  )      ->				List[Any]:
									AcceleratorState._reset_state(_lowercase  )
									debug_launcher(_lowercase  )
									debug_launcher(partial(_lowercase       ,     num_processes=1       ,     split_batches=_lowercase  )       ,     num_processes=1  )





						def 	UpperCamelCase__			(  self  )      ->				Any:
									AcceleratorState._reset_state(_lowercase  )
									debug_launcher(_lowercase  )
									debug_launcher(partial(_lowercase       ,     num_processes=1       ,     split_batches=_lowercase  )       ,     num_processes=1  )





						def 	UpperCamelCase__			(  self  )      ->				Any:
									AcceleratorState._reset_state(_lowercase  )
									debug_launcher(partial(_lowercase       ,     step_scheduler_with_optimizer=_lowercase  )  )





						def 	UpperCamelCase__			(  self  )      ->				str:
									AcceleratorState._reset_state(_lowercase  )
									debug_launcher(partial(_lowercase       ,     step_scheduler_with_optimizer=_lowercase  )  )





						@require_huggingface_suite
						def 	UpperCamelCase__			(  self  )      ->				Optional[int]:
									AcceleratorState._reset_state(_lowercase  )
									debug_launcher(partial(_lowercase       ,     num_processes=1  )  )
									debug_launcher(_lowercase  )


