

import math


class 			_SCREAMING_SNAKE_CASE      :







						def __init__(			self     ,						_SCREAMING_SNAKE_CASE							)->							Tuple:
													lowerCamelCase_								=len(_SCREAMING_SNAKE_CASE							)
													lowerCamelCase_								=[0] * (
													    4 * self.N
													)  # approximate the overall size of segment tree with array N
													self.build(1     ,						0     ,						self.N - 1							)







						def        _snake_case				(			self     ,						_SCREAMING_SNAKE_CASE							)->							List[Any]:
													return idx * 2







						def        _snake_case				(			self     ,						_SCREAMING_SNAKE_CASE							)->							Union[str, Any]:
													return idx * 2 + 1







						def        _snake_case				(			self     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE							)->							List[Any]:  # noqa: E741
													if l == r:
																				lowerCamelCase_								=A[l]
													else:
																				lowerCamelCase_								=(l + r) // 2
																				self.build(self.left(_SCREAMING_SNAKE_CASE							)     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE							)
																				self.build(self.right(_SCREAMING_SNAKE_CASE							)     ,						mid + 1     ,						_SCREAMING_SNAKE_CASE							)
																				lowerCamelCase_								=max(self.st[self.left(_SCREAMING_SNAKE_CASE							)]     ,						self.st[self.right(_SCREAMING_SNAKE_CASE							)]							)







						def        _snake_case				(			self     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE							)->							int:
													return self.update_recursive(1     ,						0     ,						self.N - 1     ,						a - 1     ,						b - 1     ,						_SCREAMING_SNAKE_CASE							)







						def        _snake_case				(			self     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE							)->							Union[str, Any]:  # noqa: E741
													if r < a or l > b:
																				return True
													if l == r:
																				lowerCamelCase_								=val
																				return True
													lowerCamelCase_								=(l + r) // 2
													self.update_recursive(self.left(_SCREAMING_SNAKE_CASE							)     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE							)
													self.update_recursive(self.right(_SCREAMING_SNAKE_CASE							)     ,						mid + 1     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE							)
													lowerCamelCase_								=max(self.st[self.left(_SCREAMING_SNAKE_CASE							)]     ,						self.st[self.right(_SCREAMING_SNAKE_CASE							)]							)
													return True







						def        _snake_case				(			self     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE							)->							Tuple:
													return self.query_recursive(1     ,						0     ,						self.N - 1     ,						a - 1     ,						b - 1							)







						def        _snake_case				(			self     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE							)->							str:  # noqa: E741
													if r < a or l > b:
																				return -math.inf
													if l >= a and r <= b:
																				return self.st[idx]
													lowerCamelCase_								=(l + r) // 2
													lowerCamelCase_								=self.query_recursive(self.left(_SCREAMING_SNAKE_CASE							)     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE							)
													lowerCamelCase_								=self.query_recursive(self.right(_SCREAMING_SNAKE_CASE							)     ,						mid + 1     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE							)
													return max(_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE							)







						def        _snake_case				(			self							)->							int:
													lowerCamelCase_								=[]
													for i in range(1     ,						N + 1							):
																				show_list += [self.query(_SCREAMING_SNAKE_CASE     ,						_SCREAMING_SNAKE_CASE							)]
													print(_SCREAMING_SNAKE_CASE							)


if __name__ == "__main__":
	__A	:   Any	=					[1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
	__A	:   Any	=					15
	__A	:   Dict	=					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()



from math import factorial




def        __UpperCamelCase     (      _A					:							Union[str, Any]      ,  _A					:							Tuple		)				->Any:



							"""simple docstring"""
							return factorial(_A		) / (factorial(_A		) * factorial(n - r		))




def        __UpperCamelCase     (      )				->Any:



							"""simple docstring"""
							lowerCamelCase_								=0

							for i in range(1      ,  101		):
														for j in range(1      ,  i + 1		):
																					if combinations(_A      ,  _A		) > 1E6:
																												total += 1
							return total


if __name__ == "__main__":
	print(solution())
