문제
새로운 캠페인 광고의 한 부분으로, 그드니아의 한 대기업은 자신의 로고를 도시의 어딘가에 새기고 싶어했다. 회사는 광고에 편성된 올해 예산을 모두 로고에 투자했기 때문에, 이 로고는 엄청나게 커야만 한다. 한 매니저는 모든 빌딩을 로고의 한 부분으로 사용하기로 결정했다.
로고는 n개의 서로 다른 높이를 가진 줄무늬(수직선)로 이루어진다. 각 수직선은 왼쪽부터 오른쪽으로 1부터 n까지의 번호가 붙어 있다. 로고는 1, 2, …, n의 순열 (s1, s2, …, sn)으로 나타내어진다. s1은 가장 작은 수직선, s2는 두 번째로 작은 수직선, …, sn은 가장 긴 수직선을 의미한다. 수직선들의 실제 높이는 중요하지 않다.
그드니아의 대로에는 m개의 빌딩이 있다. 놀랍게도, 모든 빌딩의 높이는 다르다. 문제는 로고와 빌딩이 매칭되는 모든 위치를 찾는 것이다.
회사를 도와 로고와 매칭되는 모든 빌딩의 연속한 구간을 찾아주자. 빌딩의 연속한 구간과 로고가 매칭된다는 것은, 구간에서 s1번째 빌딩은 구간 내에서 가장 낮고, s2번째 빌딩은 구간 내에서 2번째로 낮고, …, 마지막으로 sn번째 빌딩은 가장 커야 한다. 예를 들어, 빌딩의 연속한 구간에서 빌딩의 높이가 (5, 10, 4)이고, 로고가 (3, 1, 2)라면, 둘은 매칭된다. 3번째 빌딩의 높이는 4로 제일 작고, 1번째 빌딩의 높이는 5로 2번째로 작고, 2번째 빌딩의 높이는 10으로 가장 크기 때문이다.
입력
첫 번째 줄에는 로고의 길이를 나타내는 정수 n과 빌딩의 개수를 나타내는 정수 m이 주어진다(2 ≤ n ≤ m ≤ 1,000,000).
두 번째 줄에는 로고의 정보 si를 나타내는 정수 n개가 한 줄로 주어진다.
세 번째 줄에는 빌딩의 높이 hi를 나타내는 정수 m개가 한 줄에 주어진다.
여기서, 모든 i ≠ j에 대해 1 ≤ si ≤ n, si ≠ sj를 만족하며, hi는 모두 다르다.
출력
첫 번째 줄에 매칭되는 구간의 개수 k를 출력한다. 두 번째 줄에 구간의 시작 위치를 1-index로 출력한다. 만약 k가 0이라면, 빈 줄을 출력해야 한다.
예제
5 10
2 1 5 3 4
5 6 3 8 12 7 1 10 11 9
2
2 6
예제에서 6, 3, 8, 12, 7과 7, 1, 10, 11, 9는 로고 (2, 1, 5, 3, 4)와 매칭된다.
자세하게는, 2번째 빌딩(높이 3/1)이 가장 짧고, 1번째(높이 6/2)가 두번째로 짧고, 5번째(높이 7/9)가 세번째로 짧고, ...
로그인해야 코드를 작성할 수 있어요.