SOLVE
LATER
This is an Approximate problem!
The Museum of Tomorrow (Museu do Amanhã) is a science museum in the city of Rio de Janeiro, Brazil. The main exhibition takes visitors through five main areas: Cosmos, Earth, Anthropocene, Tomorrow and Now via a number of experiments and experiences. The museum mixes science with an innovative design to focus on sustainable cities.
Today, manager of the museum is planning to conduct a quiz in which visitors can participate and win free ticket to the museum.
There are $$n$$ cards on the table and each card has a unique integer ( from $$1$$ to $$n$$ ) written on it. The cards represent a permutation $$p$$ of size $$n$$. A visitor can perform many operations. In one operation, a visitor will select a continuous segment of cards and reverse the order of the cards. The task is to convert $$p$$ into identity permutation ( i.e. all the cards have to be in strictly increasing order ).
To decide the winner of the quiz, the manager will give a score to the sequence of operations. The score will depend on the length of continuous segments the visitor will select and another permutation $$a$$ of size $$n$$.
The score is computed in the following way:
Let's define a sequence of lengths of all the continuous segments selected by a visitor as $$lens$$ and an infinite sequence $$b$$: $$b_i = a_{i \mod n}$$. Consider a sub-sequence of $$b$$ which is equal to $$lens$$ and have the smallest position of the last element. Let the smallest possible position of last element be $$pos$$. Then, the score of the operation will be $$10^5 \cdot \frac{n^2}{pos+1}$$.
The visitor who's score is maximum will win and will get a free ticket to the museum.
Input format
The first line of input contains the single integer $$n$$ ($$1 \leq n \leq 100)$$.
The second line of input contains $$n$$ integers $$p_i$$ ($$1 \leq p_i \leq n$$) - permutation $$p$$.
The third line of input contains $$n$$ integers $$a_i$$ ($$1 \leq a_i \leq n$$) - permutation $$a$$.
Output format
In the first line of input print single integer $$q$$ ($$0 \leq q \leq 10^5$$) - number of operations.
Then print $$q$$ lines. In the $$i$$-th of them print two integers $$l_i$$ and $$r_i$$ ($$1 \leq l_i \leq r_i \leq n$$) - continuous segment of cards which you want to reverse.
Note that $$lens_i = r_i - l_i + 1$$.
Scoring
This is approximate problem and total score is sum of score of all test-cases and points of a solution is scaled based on best solution. Details of scoring is mentioned above.
Tests
There are $$100$$ tests. For each test independently: $$n$$ was generated randomly from interval $$[90, 100]$$. After both $$p$$ and $$a$$ were generated randomly.
After contest ending we will add $$100$$ more random tests in same manner but with new seeds.
$$lens$$ = $$(3, 2, 1)$$
$$b$$ = $$(2, 1, 3, 2, 1, 3, 2, 1, 3, ...)$$
Find the subsequence: $$(2, 1, [3], [2], [1], 3, 2, 1, 3, ...)$$. So $$pos=5$$ and score for this test will be $$10^5 \cdot \frac{3^2}{5+1}= 150000 $$.