# Minimum Operations to Transform Array
## Problem Statement
You are given two integer arrays, $source$ and $target$, each of length $n$. Your goal is to transform the $source$ array into the $target$ array using the minimum number of operations. If it's impossible to make the arrays equal, you should report $-1$.
There are two types of operations available:
1. **Prefix Operation**: Choose an index $i$ ($0 \le i < n$) and add $1$ to all elements in the prefix of the $source$ array from index $0$ to $i$. That is, for all $j$ such that $0 \le j \le i$, set $source_j \leftarrow source_j + 1$.
2. **Suffix Operation**: Choose an index $i$ ($0 \le i < n$) and add $1$ to all elements in the suffix of the $source$ array from index $i$ to $n-1$. That is, for all $j$ such that $i \le j < n$, set $source_j \leftarrow source_j + 1$.
Find the minimum total number of operations required to make $source$ identical to $target$.
## Input Format
The input consists of three lines:
- The first line contains a single integer $n$ ($1 \le n \le 10^5$), representing the length of the arrays.
- The second line contains $n$ integers $source_0, source_1, \dots, source_{n-1}$ ($-10^9 \le source_j \le 10^9$), representing the elements of the $source$ array.
- The third line contains $n$ integers $target_0, target_1, \dots, target_{n-1}$ ($-10^9 \le target_j \le 10^9$), representing the elements of the $target$ array.
## Output Format
Print a single integer: the minimum number of operations required. If it is impossible to make the $source$ array equal to the $target$ array, print $-1$.
## Sample Test Cases
### Sample Input 1
```
3
1 2 2
2 2 3
```
### Sample Output 1
```
2
```
### Sample Input 2
```
4
1 2 3 4
1 1 1 1
```
### Sample Output 2
```
-1
```
## Constraints
- $1 \le n \le 10^5$
- $-10^9 \le source_j, target_j \le 10^9$
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
### Sample 1
Given $n=3$, $source = [1,2,2]$, $target = [2,2,3]$.
First, calculate the difference array $b_j = target_j - source_j$ for each $j$ from $0$ to $n-1$:
$b = [2-1, 2-2, 3-2] = [1,0,1]$.
Since all $b_j \ge 0$, it's possible to transform $source$ to $target$. (If any $b_j < 0$, it would be impossible, as operations only add $1$).
Now, we define a new array $d$ of size $n+1$ based on these differences:
- $d_0 = b_0$
- $d_k = b_k - b_{k-1}$ for $1 \le k < n$
- $d_n = -b_{n-1}$
For the given example:
- $d_0 = b_0 = 1$
- $d_1 = b_1 - b_0 = 0 - 1 = -1$
- $d_2 = b_2 - b_1 = 1 - 0 = 1$
- $d_3 = -b_{n-1} = -b_2 = -1$
So, the array $d$ is $[1, -1, 1, -1]$.
The minimum number of operations is the sum of all positive elements in $d$:
$$\text{operations} = \sum_{k=0}^{n} \max(0, d_k)$$
For $d = [1, -1, 1, -1]$:
$\text{operations} = \max(0, 1) + \max(0, -1) + \max(0, 1) + \max(0, -1)$
$\text{operations} = 1 + 0 + 1 + 0 = 2$.
Here's one way to achieve this in 2 operations:
1. Apply a prefix operation with $i=0$: $source_0 \leftarrow source_0 + 1$.
$source = [1,2,2] \rightarrow [2,2,2]$.
2. Apply a suffix operation with $i=2$: $source_2 \leftarrow source_2 + 1$.
$source = [2,2,2] \rightarrow [2,2,3]$.
The $source$ array is now equal to $target$.
### Sample 2
Given $n=4$, $source = [1,2,3,4]$, $target = [1,1,1,1]$.
Calculate the difference array $b_j = target_j - source_j$:
$b = [1-1, 1-2, 1-3, 1-4] = [0, -1, -2, -3]$.
Since $b_1 = -1 < 0$, $b_2 = -2 < 0$, and $b_3 = -3 < 0$, it is impossible to make $source$ equal to $target$ because the allowed operations only add $1$ to elements, never subtract. Thus, the answer is $-1$.
Loading problem statement...