Algorithms and Data Structures

Range Maximum Queries

You are given an array of n elements and q queries. There are two types of queries:
  1. Get the maximum value in the given range
  1. Update the array at the given location
Your task is to process the queries efficiently.

Input

The first line of the input contains two integers n and q (1 ≤ n, q ≤ 100 000), representing the number of elements in the array and the number of queries, respectively.
The second line contains n space-separated integers (), representing the initial elements of the array.
The following q lines each represent a query:
  1. For range maximum queries: The line starts with the number 1 followed by two integers and (), representing the range of indices [] for which the maximum value needs to be calculated.
  1. For array update queries: The line starts with the number 2 followed by two integers and (), representing the position of the element to be updated and its new value.

Output

For each range maximum query, print the maximum value within the given range on a separate line.

Examples

Input
Output
6 4 1 4 2 7 5 3 1 1 3 2 2 9 1 2 5 1 3 6
4 9 7
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue