Min Max Convert
시간 제한1초메모리 제한512 MB
수열 A를 구간 최솟값 또는 최댓값으로 채우는 연산만으로 수열 B로 바꿀 수 있는지 판정하고, 2N개 이하의 연산을 출력합니다.
문제
Let A be a sequence of N elements. You can perform two types of operations on this sequence:
- Select an interval of positions [a, b](1 ≤ a ≤ b ≤ N). Let x be the maximum value on this interval. Replace all the elements in the interval with x.
- Select an interval of positions [a, b](1 ≤ a ≤ b ≤ N). Let x be the minimum value on this interval. Replace all the elements in the interval with x.
Determine a sequence of operations such that sequence A becomes another given sequence B (of also N elements). The number of operations must be less or equal than 2 ∗ N.
입력
The first line of the input contains a single number N. The second line contains A, a sequence of N elements. The third line contains B, another sequence of N elements.
출력
If there is no solution such that sequence A becomes B, print –1. Otherwise, print on the first line a single number x, the minimum number of operations needed to transform sequence A in B. Each of the next x lines will contain a character (the type of the operation: m if the operation use the minimum and M for the maximum) and an interval (a, b), describing the operations needed for the process. If there are multiple solutions, print any of them.
제한
- 1 ≤ N ≤ 100.000
- All values in A and B are integer numbers from [1, N]