An Alternative Way

Let $d_i=b_i-a_i$. We need to represent the whole difference array $d$ as a sum of operation effects.

One operation on a segment $[l,r]$ contributes

$+1,-1,+1,-1,\ldots$

starting from index $l$.

Remove the alternating signs

Use 1-indexing and define

$x_i=(-1)^i d_i$.

For an operation starting at $l$, its contribution to $d_i$ is $(-1)^{i-l}$ for every $i$ inside the segment. After multiplying by $(-1)^i$, its contribution to $x_i$ becomes

$(-1)^i(-1)^{i-l}=(-1)^l$.

So in the transformed array $x$:

• if $l$ is even, the operation adds $+1$ to the whole segment;
• if $l$ is odd, the operation adds $-1$ to the whole segment.

Now the problem is: can we build array $x$ using positive intervals that may only start at even positions, and negative intervals that may only start at odd positions?

That is already much nicer.

The tempting wrong idea

You might think: if $x_i>x_{i-1}$, then a positive interval must start at $i$, so $i$ must be even. Nope. Ending a negative interval also increases the value. Similarly, ending a positive interval decreases the value.

For example, $x=[-1,0,1]$ is possible: use a negative interval on $[1,2]$ and a positive interval on $[2,3]$. The increase at index $3$ happens because the negative interval ended. So yeah, the naive adjacent-difference check gets cooked.

Active intervals

At any position, let:

• $P$ = number of active positive intervals;
• $N$ = number of active negative intervals.

Then the current value is

$x_i=P-N$.

For a fixed $x_i$, knowing $P$ determines $N$:

$N=P-x_i$.

So instead of tracking both counts, we can track possible values of $P$.

The key fact is that after processing a position $i$, all possible values of $P$ form an interval:

$[\max(0,x_i), U]$,

where $U$ is the maximum possible active positive count.

The lower bound is forced because $P\ge 0$ and $N=P-x_i\ge 0$, so $P\ge x_i$ too.

Now we only need to update $U$ while scanning left to right.

Odd index transition

At an odd index, only negative intervals may start.

That means $P$ cannot increase. We can end some positive intervals, so $P$ can decrease, but it cannot go above the previous maximum $U$.

To realize $x_i$, we need some valid $P\ge \max(0,x_i)$. This is possible iff

$\max(0,x_i)\le U$.

Equivalently, since $U\ge 0$, this only fails when $x_i>U$.

If it works, the maximum possible $P$ stays the same:

$U'=U$.

Even index transition

At an even index, only positive intervals may start.

Now negative intervals cannot start; they can only continue or end. So the limiting resource is how many active negative intervals we could have had from the previous position.

At the previous position, the maximum possible positive count was $U$, and the previous value was $x_{i-1}$. Therefore the maximum possible negative count was

$U-x_{i-1}$.

Call this maxNeg.

At index $i$, choose any final negative count $N$ from $0$ to maxNeg. Then to get value $x_i$, we need

$P=x_i+N$.

So the maximum possible new positive count is

$U'=x_i+(U-x_{i-1})$.

This transition is possible iff at least one valid nonnegative $P$ exists, i.e.

$U'\ge \max(0,x_i)$.

If not, answer is NO.

Why this is enough

The scan keeps exactly the useful information: how much positive interval capacity we can still have active while matching everything so far.

At odd indices, we can freely start negative intervals to lower the value, but cannot create new positive ones.

At even indices, we can freely start positive intervals to raise the value, but cannot create new negative ones.

Ending intervals is always flexible: any active interval can stop before the current position, and after the final position all remaining active intervals can end at $n$. So there is no extra final condition.

Algorithm

For each test case:

1. Read $a$ and $b$.
2. Compute each transformed value:
   • odd $i$: $x_i=a_i-b_i$;
   • even $i$: $x_i=b_i-a_i$.
3. Maintain:
   • prev = previous $x$ value;
   • U = maximum possible active positive intervals.
4. Initially prev = 0, U = 0.
5. For each index:
   • if $i$ is odd, require $x_i\le U$;
   • if $i$ is even, set newU = x_i + U - prev, and require newU >= max(0, x_i).
6. If every position works, print YES; otherwise print NO.

Complexity: $O(n)$ per test case, $O(n)$ memory for storing $a$, and all counts fit in long long.