There is a town on the positive x-axis with $n$ houses, house $i$ is at point $i$, and there's a road between every two adjacent houses.
Jaber went to the town to explore the houses, this is what you know about his trip:
Teleportation costs a lot of fuel, so Jaber chose the starting house $x$ and the path he took in a way to minimize the number of times he teleported.
You're given for each road how many times he used it, print the minimum possible number of times he teleported.
Note: Jaber didn't necessarily visit all the houses.
The first line of input contains $n$ ($2 \le n \le 3 \cdot 10^5$), the number of houses in the town.
The second line contains $n-1$ integers $a_1, a_2, ..., a_{n-1}$ ($0 \le a_i \le 10^9$), the number of times Jaber used road $i$, where road $i$ is the road that connects city $i$ and city $i+1$. It's guaranteed that at least one value $a_i$ is positive.
Print a single integer, the minimum number of times Jaber could have used the teleportation device.
In the first example, one possible path that Jaber could have taken is:
There are other paths he could have taken and other houses he could have started at that also need a single teleportation.
| Input | Output |
|---|---|
5 2 1 0 3 Copy
|
1 Copy
|
3 1000000000 1000000000 Copy
|
0 Copy
|
Let's say that we started at house $i$ and ended at house $j$ without teleporting, and that $i < j$, then all roads to the left of house $i$ and to the right of house $j$ have been visited an even number of times, and all roads between house $i$ and $j$ have been visited an odd number of times, the number of times can be anything for each road as long as the parity is correct.
That means we can select a segment of roads, divide this segment into three segments and visit each road in the first and third segment an even number of times, and each road in the second segment an even number of times. If we teleport $x$ times, we can use this operation $x+1$ times, so the solution is to find minimum number of such segments we can divide the array into. Let's call such segments good segments, basically divide the array into multiple segments by removing zero values, let's call these segments big segments, then for each big segment remove even values, the number of good segments in this big segment is the number of resulting segment(from removing even values) $-$ $1$.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
int const N = 300000;
int x[N];
int main(){
int n;
scanf("%d", &n);
--n;
f(i, 0, n){
scanf("%d", x + i);
if (x[i])x[i] = 2 - (x[i] & 1);
}
n = unique(x, x + n) - x;
int an = -1;
f(i, 0, n){
int o = 0;
if (x[i] == 0)continue;
while (i < n && x[i]){
if (x[i] == 1)++o;
++i;
}
an += max(0, o - 1) + 1;
}
printf("%d\n", an);
}