Optimal Viewing of Russian Dolls

The Russian doll is a nested doll. In this problem, you are given a set of n dolls with distinct sizes. We label the dolls by their sizes from 1 to n in increasing order. A doll of size \(x\) may contain any number of dolls with sizes lower than \(x\). In our construction, the dolls are arranged in a chain: the doll of size \(n\) (the largest) initially comes on the table, and it contains the doll of size \(n-1\), the doll of size \(n-1\) contains the doll of size \(n-2\), and so on.

When ATM wants to view a doll of size \(k\), he first checks if the doll is already on the table. If it is, he can view it immediately without opening any doll. Otherwise, he will choose one of the dolls on the table that is still closed (i.e. not opened before) and open it. Opening a doll takes out all of its immediately contained dolls and places them on the table. Note that if these dolls themselves contain other dolls, those nested dolls remain inside unless they are opened later.

ATM is extremely meticulous and will always minimize the number of doll openings required. There are two types of queries. Sometimes, he only wishes to know the minimum number of openings needed to eventually see the doll of size \(k\) (without actually opening anything); other times, upon hearing that a certain doll is especially beautiful, he will actually perform the openings. Your task is to output, for each query, the minimum number of doll openings needed.

Note: Initially, the only doll on the table is the doll of size \(n\), and it is closed. In our chain structure, if no doll has been opened so far, only the doll of size \(n\) is on the table. Opening a doll of size \(m\) will reveal the doll of size \(m-1\) (if \(m > 1\)).

The input starts with two integers \(n\) and \(q\). Then there are \(q\) queries. Each query consists of two integers \(op\) and \(k\):

• If \(op = 0\), ATM only inquires about the minimum number of openings needed in order to view the doll of size \(k\) (without actually opening any doll).
• If \(op = 1\), ATM actually performs the openings (and the table configuration is updated accordingly) while the number of openings performed is still minimized.

For example, consider \(n = 5\) and the following queries:

0 3
1 3
0 2

Initially, only the doll of size 5 is on the table and the doll of size 5 contains the doll of size 4, which in turn contains the doll of size 3, and so on. To view the doll of size 3, ATM must open the doll of size 5, and then the doll of size 4, totaling 2 openings. In the inquiry query (op = 0) he learns that 2 openings are needed but does not change the configuration. In the actual opening query (op = 1), he opens the two dolls and the doll of size 3 becomes available on the table. Subsequent queries will see the updated configuration.

inputFormat

The first line contains two integers \(n\) and \(q\) (\(1 \leq n, q \leq 10^5\)) indicating the number of dolls and the number of queries respectively.

Each of the following \(q\) lines contains two integers \(op\) and \(k\) (\(1 \leq k \leq n\); \(op\) is either 0 or 1), where:

• If \(op = 0\), then output the minimum number of openings needed to have the doll of size \(k\) on the table (without changing the state).
• If \(op = 1\), then simulate the doll openings (minimally) to bring the doll of size \(k\) onto the table and output the number of openings performed.

outputFormat

For each query, output the minimum number of doll openings needed on a separate line.

sample

5 3
0 3
1 3
0 2

2
2
1