Nagatoro is practising some form of interpretive art. She currently has a canvas with a binary array (consisting of only s and s) of length , and she wants to turn it into some beautiful binary array of the same length. To do this, she borrowed a magical brush from Senpai. With one stroke of the brush from index to index , she can rearrange the numbers from index to index in non-decreasing order. Due to the minimalistic requirements of modern art, she would like to use the least number of brush strokes possible. Please help her find the minimum number of brush strokes to turn into , as well as a minimal sequence of strokes that accomplishes this task.
Subtask 1 [40%]
Subtask 2 [60%]
No additional constraints.
The first line contains an integer .
The second line contains integers , representing the array .
The third line contains integers , representing the array .
If it is impossible to turn into , output
Otherwise, on the first line output an integer , the minimum number of brush strokes to turn into .
Then, on the -th of the next lines, output integers and , representing that the -th brush stroke in your solution goes from index to index .
The array after applying the brush strokes in order should satisfy for all . If there are multiple possible outputs satisfying these requirements, any of them will be accepted.
Sample Input 1
7 0 1 0 1 0 1 0 0 0 0 1 1 0 1
Sample Output 1
2 5 7 1 5
Explanation for Sample 1
Initially, is .
After the first brush stroke, becomes .
After the second brush stroke, becomes .
This is a valid output since for all after the given brush strokes, and it can be proven that is the minimum number of brush strokes possible.
Sample Input 2
3 1 0 1 0 1 0
Sample Output 2