Balada lu' State

Time limit: 1.5s Memory limit: 256MB Input: Output:

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

Cerință

Fie AA si BB doi vectori de lungime NN. Un interval [l,r][l,r] este considerat sigma\textbf{sigma} dacă min(Bl,,Br)max(Al,,Ar)max(Bl,,Br)\min(B_l,\dots,B_r) \leq \max(A_l,\dots,A_r) \leq \max(B_l,\dots,B_r).

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

Date de intrare

Pe prima linie se află tt, numărul de test cases. Pe prima linie a fiecărui test case se află NN, numărul de elemente din cei doi vectori. Pe următoarea linie se află elementele vectorului AA, urmând pe ultima linie elementele din vectorul BB.

Date de ieșire

Se vor afișa tt numere, sumele cerute.

Restricții și precizări

  • 1t1001 \leq t \leq 100
  • 1N1051 \leq N \leq 10^5
  • 1Ai,Bi1091 \leq A_i,B_i \leq 10^9
  • Se garantează faptul că suma NN-urilor pe toate test case-urile este 105\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 sigma\textbf{sigma} sunt [1,7][1,7] și [8,11][8,11].

Log in or sign up to be able to send submissions!