## DMOPC '21 Contest 2 P6 - Strange Function

View as PDF

Points: 30 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

You are given a permutation of . Consider the following function:

void f(int l,int r) {
if (l >= r) return;
int i = min_element(p+l,p+r+1)-p; // position of minimum element in [l,r]
rotate(p+l,p+i,p+i+1); // cyclically shift [l,i] to the right by 1, so that the minimum element gets moved to position l
f(i+1,r); // continue on [i+1,r]
}


For example, calling on the permutation gives a result of . Note that remains a permutation of when is called on it several times.

Process queries of the form:

• 1: Call once.
• 2 i: Output the current value of .
• 3 i: Output the unique index such that .

#### Constraints

is a permutation of .

For all type 2 and type 3 queries, .

All type 1 queries appear before all type 2 and type 3 queries.

There are only type 1 and type 2 queries.

There are only type 1 and type 3 queries.

#### Input Specification

The first line contains two space-separated integers: and .

The second line contains space-separated integers: .

The next lines each describe a query.

#### Output Specification

For each type 2 or type 3 query, output the answer on a new line.

#### Sample Input

6 16
4 2 1 3 6 5
3 1
3 2
3 3
3 4
3 5
3 6
1
2 1
2 2
2 3
2 4
2 5
2 6
1
2 3
3 3

#### Sample Output

3
2
4
1
6
5
1
4
2
3
5
6
4
4

#### Explanation

Initially, is . We have

• appears at index , so the answer to the first query is .
• appears at index , so the answer to the second query is .
• appears at index , so the answer to the third query is .
• appears at index , so the answer to the fourth query is .
• appears at index , so the answer to the fifth query is .
• appears at index , so the answer to the sixth query is .

After calling once, is .

After calling a second time, is .