All Tracks>Data Structures> Advanced Data Structures> Fenwick (Binary Indexed) Trees> Problem
Mr. Sinister and his World
★★★★★

3

1 votes
Binary Search, Bit Manipulation, Data Structures, Fenwick tree, Medium, Sets
Problem

It is a very bad time for human race, as powerful mutant Mr. Sinister has taken control of the world. He is killing a lot of people. The world is one dimensional and at most one man can stay at one point of the world. The points are numbered from (1,0) to (INF,0) where INF denotes infinity.

As Sinister is killing humans, he wants to know the maximum distance between any two adjacent humans in the world. But a human can come or leave the world (goes to another planet) at a time. So, there will be three types of queries of the following form.

  • 1 X - A human comes and occupies co-ordinate (X,0). It is guaranteed that before this query, there will be no human at the given point.

  • 2 - You have to find out the maximum distance between any two adjacent humans and the position of these two humans. If there is a tie in the maximum adjacent distances, then print the one which has maximum X co-ordinate.

Example - Suppose there are points with X co-ordinates [1, 4, 7, 10], then 3 is maximum distance and adjacent X coordinates which give this maximum distance are 7 and 10.

  • 3 X - A human who currently occupies co-ordinate (X,0) leaves the world. It is guaranteed that there will be a human at co-ordinate (X,0) before this query.

Also, It is guaranteed that at any particular time there will at least two humans in the world.

As Mr. Sinister is not a very good programmer, can you help answer all queries of type 2 for him?

Input: :

First line of the input contains a single integer T denoting the number of test cases in the input.

Each test case starts with an integer N denoting the number of people initially in the world.

The next line consists of N distinct space separated integers Ci, denoting the X co-ordinates of the initially present people.

The next line contains a single integer Q denoting the number of queries.

For each query, first integer will be type denotes the type of that query.

If type is 1 or 3, then there will be another integer X denoting the X co-ordinate where a human will come or leave depending upon the type of query.

Output:

For each query of type 2, print three integers, the maximum distance between any two adjacent humans and the co-ordinate of this two humans. The co-ordinate have to be printed in increasing order.

Constraints:

1≤T≤3

2≤N,Q≤105

1≤Ci,X≤106

1≤type≤3

Sample Input
1
2
1 2
11
1 10
1 5
1 9
2
1 13
2
3 10
2
1 20
2
3 9
Sample Output
Case 1:
4 5 9
4 5 9
4 9 13
7 13 20
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Initially there are two humans in this world: [1,2]

After first query : [1,2,10]
After second query: [1,2,5,10]
After third query: [1,2,5,9,10] After fourth query: Maximum distance is 4 and adjacent points are 5 and 9
After fifth query: [1,2,5,9,10,13]
After sixth query: Maximum distance is 4 and adjacent points are is 5 and 9
After seventh query: [1,2,5,9,13]
After eighth query: Maximum distance is 4 and adjacent points are is 9 and 13
After ninth query: [1,2,5,9,13,20] After tenth query: Maximum distance is 7 and adjacent points are is 13 and 20
After eleventh query: [1,2,5,13,20]

Contributers:
Editor Image

?