You are given an array a1, a2, …, aN consisting of N elements. You are given Q queries. Each query is of the following types:
Input format
Output format
For every query of Type 3, print an integer denoting the maximum distance j−i+1 where 1≤i, j≤n.
Note: The query of type 3 is present at least once in the problem.
Constraints
1≤N≤4000001 ≤ ai ≤ 1091≤L, R≤N1≤Q≤100001≤x, y, z≤1000000000
Note: No ai exceeds 1018 after updates.
after 1st query, the array becomes:
2 3 3 4 5
after 2nd query, the array becomes:
6 9 9 12 5
3rd query: the distance is 2 (a2 = 9 & a3 = 9)
after 4th query, the array becomes:
6 9 9 12 6
5th query: the distance is 5 (a1 = 6 & a5 = 6)