Problem 76: Emacs

Martie 1993,
Tradiția făcea ca micul rms își petrecea iar timpul în editorul de text mai bun. Observând obsesia îngrijorătoare, apropiațiilor le mai scăpară vorbe: ” Mai ieși și tu din editorul ăla, ceilalți copii de vârsta ta mai fac și altele, mai stau pe telefonul mobil, mai intră în browser!”. rms nu consideră că e vreo problemă, nici ceilalți de vârsta lui nu ar fi putut ieși din editor, pentru că nu știau comanda. Era însă o zi specială, de Sfântul IGNUcius, rms nu ar fi conceput să se ocupe cu treburi superficiale. Discuțiile aprinse pe email cu ceilalți pedanți păreau să nu aibe vreun deznodământ și îi captaseră întreaga atenție. Urma să prezinte cea mai nouă funcționalitate la care a lucrat, M-x compune-o-problemă-random și rezultatul (îndrăznim să zicem, pe măsură!), obținut.

Se consideră două șiruri de N numere naturale, V și E. Se cere suma valorilor maxime din V pentru toate subsecvențele determinate de capetele $1 ≤ i_1 ≤ i_2 ≤ N$ unde $E_{i_1} = E_{i_2}$ .

Date de intrare

Pe prima linie se află numărul de elemente N. Pe fiecare dintre următoarele două linii se află N numere naturale, reprezentând elementele șirului V , respectiv E.

Date de ieșire

Pe prima linie se va afișa rezultatul cerut, modulo 1 000 000 007.

Restricții și precizări

$1 ≤ N ≤ 3 \cdot 10^5$
$1 ≤ V_i, E_i ≤ 10^9$ pentru 1 ≤ i ≤ N
O subsecvență este un subșir format din elemente cu indici consecutivi.

Subtask 1 (8 puncte)

N ≤ 2 000

Subtask 2 (11 puncte)

$E_i = 1$ pentru 1 ≤ i ≤ N

Subtask 3 (12 puncte)

$E_i ≤ 20$ pentru 1 ≤ i ≤ N

Subtask 4 (12 puncte)

$V_i ≤ 20$ pentru 1 ≤ i ≤ N

Subtask 5 (19 puncte)

$N ≤ 5 \cdot 10^4$

Subtask 6 (38 de puncte)

Fără restricții suplimentare.

Exemplu

stdin

5
5 29 3 28 30
9 8 9 9 8

stdout

Explicații

Subsecvențele care contribuie la răspuns sunt cele unde capetele au valori egale în E. În cazul de față, tuplurile care conțin cele două capete și valoarea maximă din V sunt (1, 1, 5),(1, 3, 29),(1, 4, 29),(2, 2, 29),(2, 5, 30),(3, 3, 3),(3, 4, 28),(4, 4, 28),(5, 5, 30).

Aceste valori însumate dau 211.

Emacs