Incremental queries
Problem
You are given an array consisting of elements . You must process queries and there are two types of queries:
- : Replace element by , that is, .
- : You are required to print the minimum number of operations to make all elements equal in subarrays .
You can perform the following operation in order to make elements equal:
- Select any index and replace with or .
Note: You do not have to modify the original array in a query of type 2.
Input format
- The first line contains two space-separated integers and .
- The second line contains space-separated integers .
- Each of next lines contains three integers type , denoting the type of query and its parameters.
Output format
Print a single integer for every query of the second type.
Constraints
The types of queries are either 1 or 2.
If the type is 1:
If the type is 2:
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
Our initial array is [1,3,4,1] and now we will process the queries:
- We need to consider subarray [1,3] if we once increment first element by 2 we will get [3,3] so minimum operations required will be 1 and our array will remain [1,3,4,1].
- We need to replace and index by 4, so array will be [1,4,4,1]
- We need to consider subarray [4,4] since this subarray is already equal, number of operations are 0.
