/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
正整数 N,M と長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。A の各要素は 0 以上 M 未満であることが保証されます。
この整数列 A に対して以下の操作を 0 回以上何回でも行うことができます：
- 1\le l\le r\le N を満たす整数の組 (l,r) を選び、i=l,l+1,\ldots,r に対して A_i を (A_i+1) \bmod M で置き換える。
A を回文にするために必要な操作回数の最小値を求めてください。
ただし、A が回文であるとは i=1,2,\ldots,N に対し A_i=A_{N+1-i} が成り立つことを指します。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T
- 1\le N\le 2\times 10^5
- 1\le M\le 10^9
- 0\le A_i < M
- 全てのテストケースにおける N の総和は 2\times 10^5 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N M A_1 A_2 \ldots A_N
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
入力例 1
3 4 5 0 3 1 2 1 20260418 454 7 12 3 1 4 1 5 9 2
出力例 1
3 0 5
1 番目のテストケースについて考えます。
以下のように 3 回操作することで A を回文にすることができます：
- (l,r)=(2,4) を選ぶ。A=(0,4,2,3) となる。
- (l,r)=(3,4) を選ぶ。A=(0,4,3,4) となる。
- (l,r)=(3,4) を選ぶ。A=(0,4,4,0) となる。
3 回未満の操作で A を回文にすることはできないので、3 を出力してください。
Score : 525 points
Problem Statement
You are given a positive integer N, a positive integer M, and an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. It is guaranteed that each element of A is between 0 and M-1, inclusive.
You can perform the following operation on the integer sequence A any number of times, possibly zero:
- Choose a pair of integers (l,r) satisfying 1\le l\le r\le N, and replace A_i with (A_i+1) \bmod M for each i=l,l+1,\ldots,r.
Find the minimum number of operations required to make A a palindrome.
Here, A is a palindrome if A_i=A_{N+1-i} holds for i=1,2,\ldots,N.
You are given T test cases; solve each of them.
Constraints
- 1\le T
- 1\le N\le 2\times 10^5
- 1\le M\le 10^9
- 0\le A_i < M
- The sum of N over all test cases is at most 2\times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N M A_1 A_2 \ldots A_N
Output
Output the answers for the test cases in order, separated by newlines.
Sample Input 1
3 4 5 0 3 1 2 1 20260418 454 7 12 3 1 4 1 5 9 2
Sample Output 1
3 0 5
Consider the first test case.
You can make A a palindrome in three operations as follows:
- Choose (l,r)=(2,4). A becomes (0,4,2,3).
- Choose (l,r)=(3,4). A becomes (0,4,3,4).
- Choose (l,r)=(3,4). A becomes (0,4,4,0).
It is impossible to make A a palindrome in fewer than three operations, so output 3.