Pair Increment Ranges - Repovive Starter Round 2 | Repovive

10F. Pair Increment Ranges

3000 pts2s256 MB

You are given two arrays $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ .

An interval $[l,r]$ with $1 \le l \le r \le n$ is called beautiful if it is possible to make $a_i = b_i$ for every $l \le i \le r$ using the following operation any number of times:

Choose an index $i$ such that $l < i \le r$ , then decrease $a_{i-1}$ by $1$ and increase $a_i$ by $1$ .

The operation affects only the current interval $[l,r]$ .

For each test case, output the number of beautiful intervals.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le a_i, b_i \le 10^9$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

1
5
5

Case 2

2
1 0
0 1

Case 3

3
2 0 0
0 1 1

Case 4

4
1 2 1 2
1 2 1 2

Case 5

5
2 0 0 1 0
0 1 1 0 1

Explanation

Case 1

The only beautiful interval is $[1,1]$ , because the two arrays are already equal there.

Case 2

The only beautiful interval is $[1,2]$ . By applying the operation once, the first element decreases by $1$ and the second element increases by $1$ .

Case 3

The only beautiful interval is $[1,3]$ . Apply the operation twice with $i=2$ , then once with $i=3$ .

Case 4

Every interval is beautiful, because the two arrays are already equal everywhere and we can use zero operations.

Case 5

The beautiful intervals are $[1,3]$ , $[1,5]$ , and $[4,5]$ .

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given two arrays $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ .

An interval $[l,r]$ with $1 \le l \le r \le n$ is called beautiful if it is possible to make $a_i = b_i$ for every $l \le i \le r$ using the following operation any number of times:

Choose an index $i$ such that $l < i \le r$ , then decrease $a_{i-1}$ by $1$ and increase $a_i$ by $1$ .

The operation affects only the current interval $[l,r]$ .

For each test case, output the number of beautiful intervals.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le a_i, b_i \le 10^9$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

The only beautiful interval is $[1,1]$ , because the two arrays are already equal there.

The only beautiful interval is $[1,2]$ . By applying the operation once, the first element decreases by $1$ and the second element increases by $1$ .

The only beautiful interval is $[1,3]$ . Apply the operation twice with $i=2$ , then once with $i=3$ .

The beautiful intervals are $[1,3]$ , $[1,5]$ , and $[4,5]$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

10F. Pair Increment Ranges

Constraints

Input

Output

Samples

10F. Pair Increment Ranges

Constraints

Input

Output

Samples