RoAlgo Educational Round #3 | Balada lu' State

State smecher de Paris
De dusmani nu e invins
State nume cu respect
De baiat destept. $\newline$

Cerință

Fie $A$ si $B$ doi vectori de lungime $N$. Un interval $[l,r]$ este considerat $\textbf{sigma}$ dacă $\min(B_l,\dots,B_r) \leq \max(A_l,\dots,A_r) \leq \max(B_l,\dots,B_r)$.

Dacă $S$ reprezintă mulțimea intervalelor $\textbf{sigma}$, calculați $\displaystyle \sum_{[l,r] \in S} \max(B_l,B_{l+1},\dots,B_r)$.

Date de intrare

Pe prima linie se află $t$, numărul de test cases. Pe prima linie a fiecărui test case se află $N$, numărul de elemente din cei doi vectori. Pe următoarea linie se află elementele vectorului $A$, urmând pe ultima linie elementele din vectorul $B$.

Date de ieșire

Se vor afișa $t$ numere, sumele cerute.

Restricții și precizări

• $1 \leq t \leq 100$
• $1 \leq N \leq 10^5$
• $1 \leq A_i,B_i \leq 10^9$
• Se garantează faptul că suma $N$-urilor pe toate test case-urile este $\leq 10^5$.

Exemplu

stdin

1
11
2 3 1 6 2 1 6 2 4 2 2
4 3 1 5 2 1 8 5 2 1 2

stdout

311

Explicație

Două dintre intervalele $\textbf{sigma}$ sunt $[1,7]$ și $[8,11]$.