[2019 SCPC 2차 예선]
\(n\)개의 숫자들로 이루어진 두 개의 수열 \(a = a_1\ a_2 \cdots a_n\)와 \(b = b_1\ b_2 \cdots bn\)가 있다.
두 수열 \(a\)와 \(b\)의 유사도란 두 수열에서 같은 위치의 숫자가 일치하는 개수이다.
예를 들어, \(a = 5\ 2\ 3\ 7\ 6\ 1\)와 \(b = 5\ 7\ 1\ 2\ 6\ 3\)가 주어지면, 제일 첫 번째 숫자 5와 뒤에서 두 번째 숫자 6이 일치하므로 \(a\)와 \(b\)의 유사도는 2이다.
우리는 두 번째 수열 \(b\)에 대해서만 임의의 구간 \([i, j]\)를 선택해서 이 구간에 속한 수들을 회전시킨다.
여기서, 회전이라는 것은 이 구간에 속한 수 \(b_i\ b_{i+1}\cdots b_{j-1}\ b_j\)를 \(b_j\ b_{j-1}\cdots b\{i+1}\ b_i\)와 같이 앞쪽과 뒤쪽의 수들을 서로 맞 바꾸는 것이다.
특별한 경우로 구간 \([i, i]\)을 회전하면 수열엔 변화가 없다.
위 예의 \(b = 5\ 7\ 1\ 2\ 6\ 3\)에서 구간 \([3,6]\)을 회전하면, \(b\)는 수열 \(5\ 7\ 3\ 6\ 2\ 1\)이 되고 두 수열의 유사도는 3이 된다.
그러나 \(b\) 에서 구간 \([2,4]\)를 회전하면, \(b\)는 수열 \(5\ 2\ 1\ 7\ 6\ 3\) 이 되고 두 수열의 유사도는 4 가 된다.
두 수열 \(a\)와 \(b\)가 주어질 때, 수열 \(b\)의 구간을 선택해서 단 한번 회전한 후 두 수열의 유사도가 최대가 되도록 하고 그 때의 유사도를 출력하는 프로그램을 작성하시오.
입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 \(T\) 가 주어지고,
이후 차례로 \(T\)개의 테스트 케이스가 주어진다. \((1 \le T \le 40)\)
각 테스트 케이스의 첫 줄에는 두 수열을 이루는 숫자들의 개수 \(n\)이 주어진다. \(n\)의 범위는 1 이상 5,000 이하이다.
둘째 줄에는 첫 번째 수열 \(a\)를 나타내는 \(n\)개의 숫자들이 주어진다. 셋째 줄에는 두 번째 수열 \(b\)를 나타내는 \(n\)개의 숫자들이 주어진다.
여기서, 두 수열을 이루는 숫자들은 1이상 \(10^6\)이하의 정수이다.
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.
그 다음 줄에, 수열 \(b\)의 구간을 단 한번 회전했을 때, 두 수열 유사도의 최대값을 출력한다.
| 입력 |
|---|
| 2 6 5 2 3 7 6 2 5 7 1 2 6 3 10 2 1 1 3 2 2 3 1 1 2 2 1 2 3 1 3 1 1 2 1 |
| 출력 |
|---|
| Case #1 4 Case #2 6 |