Permutation and reverse
Tag(s):

## Hard

Problem
Editorial
Analytics

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.

SAMPLE INPUT
3
3 1 2
2 1 3

SAMPLE OUTPUT
3
1 3
1 2
1 1

Explanation

$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$.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

July Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Algorithms > Sorting
• Algorithms > Searching
• Algorithms > Graphs
• Algorithms > Dynamic Programming
• Algorithms > Graphs
• Data Structures > Trees