### PROBLEM LINK:

**Author:** Sergey Nagin

**Tester:** Sergey Kulik

**Editorialist:** Lalit Kundu

### DIFFICULTY:

MEDIUM-HARD

### PREREQUISITES:

Greedy

### PROBLEM:

You have two array of N ≤ 10^{5} integers A_{1},A_{2}…A_{N} and B_{1},B_{2}…B_{N}. In a single step Sereja can choose two indexes i and j (1 <= i <= j <= n) and we make A_{p} equal to (A_{p} + 1) modulo 4 if p is an integer from the range [i:j].

What is the mininal number of steps necessary in order to make the array A equal to the array B?

0 ≤ A_{i},B_{i} ≤ 3

### EXPLANATION:

First, we make one array instead of two in such a way that you increase the subsegments in it till it’s of the form 0-0-0-…-0. Then consider a problem without modulo that is, the problem : given a_{1},a_{2}…a_{n} and you can decrease a subsegment by one, what will be the answer?

Our answer will be sum max(0, a* - a[i - 1]) over i = 2 … n, which we arrive at greedily. How?

Here we should increase some subsegments by 4 for this sake. It’s clear that the answers for the initial array and the array where the subsegments are increased by 4 may differ but **the arrays themselves** will NOT differ because we increase by 4 modulo 4.

So now we:

- Get one array instead of two, where we will apply -1 operations, say a’.
- and we need to make it zero by applying these operations.
- Also, we have to add 4 to some subsegments in order to minimize this term: sum max(0, a
_{i}- a__{i-1}) for i = 1 … n. a_{}is fictive and equals to zero.

Let’s get the array c = a’_{} - a’_{i - 1} where a’ is the array we’ve obtained in step 1.

And increasing subsegment by 4 means decreasing some c_{j} and increasing some c_{i} where i < j.

The next part, we can see by pseudo code:

```
ans=k1=k2=0
for i = 1 to n:
if c* < 2: // if the value of c* is *small*, we can use it as it is
ret + = max ( 0, c* ) // ie. max ( 0, a* - a[i-1] )
// we can use this cell later as the beginning of some segment (segment where we increase all terms by 4)
// if it's value is an appropriate for this, let's remember it
if (c* == -3): k1++
if (c* == -2): k2++
else: // we will use this cell as end of some segment
if k1>0 : // we use this because ret will increase less if we use these cells.
// if we use some cell c[j] having c[j]=-3, where j<i, c[j] will increase by 4 and c* will decrease by 4
k1--; // one cell has been used
ret ++ // because c[j] will become 1 afterwards, earlier it was contributing 0 to ret.
c* - = 4 // this is the end of subsegment, so we decrease by 4
elif k2>0:
k2-- // used
ret += 2 // earlier contribution was 0, but now it will contribute (-2+4) to the ret.
c* -= 4 // this is the end of subsegment, so we decrease by 4
// after making the segment the value of c* might become small
// and therefore, the current cell can be a beginning of some further segment
if (c* == -3) k1 ++
if (c* == -2) k2 ++
ret += max( c* , 0 )
print ret
```