Hi there, I have this problem: Given an array A of integers. You need to operate three kinds of online query:

• Insert an element X at position i in the array
• Delete element at position i in the array
• Answer the maximum element and the index of maximum element in range [l, r]

Constraints:

• Q = number of queries — less than or equal 100000
• N = number of elements — less than or equal 100000
• X, A[i] is less than or equal 1000000000

I don't know which data structure is the most suitable for solving this problem. Can you help me with this and explain how to use that data structure?

Thank you.

UPD: This is online query problem.

UPD2: I've added tags for the blog entry.