Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Nearest Light

By amin21 · Limits 1s, 512 MB

We, iuian develop a virtual vertical line with infinite length are numbered starting from zero from left to right. At every integer point of the vertical line, there is a bulb. Initially all the bulbs are turned on.

You are given Q queries of two types:

  • 1 n (after this query nth bulb will be turned off, and remains turned off until end)
  • 2 n (print the difference between nth position and nearest turned on bulb's position. i.e. answer could be 0)

Input

Input starts with an integer Q.
next Q line contains two integer t and n.
( 1<= Q,n <= 5000000, 1<= t <= 2 )

Output

Print answers to queries of the type 2 in order they appear in the input.

Sample

InputOutput
7
2 5
1 2
1 3 
1 4
1 5
2 4
2 5
0
2
1

    Discussion

    Statistics


    6% Solution Ratio

    saiful.dhEarliest, 2w ago

    saiful.dhFastest, 0.6s

    TasdidLightest, 66 MB

    TasdidShortest, 972B

    Submit

    Login to submit