Sorted or !Sorted

Sorted or !Sorted

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

You are given an array of length \(N\) and \(Q\) queries. There are two types of query :

  • \(1\) \(i\) \(x\) - you have to update the ith index with the value \(x\)
  • \(2\) \(l\) \(r\) - check whether the subarray \([l,r]\) (inclusive) is sorted in non-decreasing order or not.

Print "YES" if the subarray \([l,r]\) is sorted at that time of the query or print "NO" otherwise for every query of 2nd type.
All queries are dependent to each other.

Input

first line takes two integer \(N,Q\) : number of elements in array, number of queries
next line takes \(N\) integers
then, next \(Q\) line takes two types of input in the following format

  • \(1\) \(i\) \(x\)
  • \(2\) \(l\) \(r\)

\(1 <= N,Q <= 2*10^5\)
\(1 <= l <= r <= N\)
\(1 <= Ai,x <= 10^9\)

Output

For each 2nd type query print "YES" if the array is sorted in non-decreasing order from l to r (inclusive) or "NO" otherwise.

Sample

Input Output
6
1 2 4 4 6 7
4
2 1 6
1 5 2
2 1 6
2 1 4
YES
NO
YES

Bangladesh 2.0

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
8
Start at
2024-08-16 15:30
End at
2024-08-16 17:45
Duration
2.2 hour(s)
Host
Partic.
133