Problem 4429: arraymode

Cerință

Se dă un șir cu $N$ numere naturale asupra căruia se definesc $M$ operații de forma:

$1$ $pos$ $x$ - valoarea de pe poziția $pos$ devine $x$
$2$ $pos$ - se cere suma secvenței maximale care începe de la poziția $pos$ cu proprietatea că orice valoare apare o singură dată, adică nu există valori duplicate

Date de intrare

Fișierul arraymode.in conține pe prima linie un număr natural $N$ reprezentând lungimea șirului.
Pe a doua linie se află $N$ numere naturale care reprezintă valorile inițiale din șir.
Pe a treia linie se află un număr natural $M$ reprezentând numărul de operații care se realizeaza asupra șirului.
Pe următoarele $M$ linii sunt descrise operațiile menționate mai sus, câte o operație pe linie. Numerele de pe aceeași linie se separă prin câte un spațiu.

Date de ieșire

În fișierul arraymode.out se va scrie pentru fiecare operație de tipul $2$ cate o linie cu răspunsul pentru acea operație, în ordinea în care apar în fișierul de intrare.

Restricții și precizări

$1 \leq N, M \leq 10^{5}$
Elementele șirului sunt numere naturale din intervalul $[1, 10^{5}]$
Pentru 25 de puncte $1 \leq N \leq 1000$
Pentru alte 35 de puncte, se garantează că după orice operație, toate elementele șirului sunt distincte
Pentru restul de 40 de puncte $1 \leq N \leq 10^{5}$

Exemplu

arraymode.in

6
10 20 30 40 50 60
6
2 2
1 4 20
2 2
2 3
1 5 20
2 4

arraymode.out

Explicație

Șirul inițial este: $10\ 20\ 30\ 40\ 50\ 60$
Pentru operația $2\ 2$ secvența maximală de elemente distincte care începe pe poziția $2$ este $10\ [20\ 30\ 40\ 50\ 60]$ cu suma elementelor $200$
După operația $1\ 4\ 20$ , șirul devine $10\ 20\ 30\ 20\ 50\ 60$
Pentru operația $2\ 2$ secvența maximală este $10\ [20\ 30]\ 20\ 50\ 60$ cu suma elementelor $50$
Pentru operația $2\ 3$ secvența maximală este $10\ 20\ [30\ 20\ 50\ 60]$ cu suma elementelor $60$
După operația $1\ 5\ 20$ , șirul devine $10\ 20\ 30\ 20\ 20\ 60$
Pentru operația $2\ 4$ , secvența maximală este $10\ 20\ 30\ [20]\ 20\ 60$ cu suma elementelor $20$

arraymode