Let $M$ be a positive integer such that $M>2$. Choose $2n$ positive integers $a_1, a_2, ..., a_n$ and $b_1, b_2, ... b_n$ not greater than $M$ such that $a_1< a_2< ...< a_n \leq M$, $b_1< b_2< ... <b_n \leq M$ and $$a_1+a_2+...+a_n=b_1+b_2+...+b_n$$
What is the maximum value of $$S=|a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|$$ that $S$ could get ?
If the condition
$a_1< a_2< ...< a_n \leq M$, $b_1< b_2< ... <b_n \leq M$
is replaced by the condition
$a_i \neq a_j$ with $i\neq j$ and $b_k \neq b_l$ with $k \neq l$ ($a_i$'s doesn't have to be different from $b_j$'s with any $i, j$)
would the maximum value of $S$ remain the same ?
I tried to use the inequality $|a|+|b| \geq |a+b|$ but it didn't work. Is it possible to find the maximum value of $S$ ?
(Edit: Thank you Sasha Kozachinskiy for your answer in the case $a_1, a_2,...,a_n$ weren't distinct integers, I have edited the question)
(sorry, English is my second language)