h2. Restricţii

* $1 ≤ N ≤ 250 000$
* $1 ≤ T ≤ 3$
* Înalţimile şi coeficienţii de frumuseţe ale bucăţilor piesei se încadreaza pe $32$ de biti cu semn;
* Pentru $20%$ din teste $N ≤ 100$;
* Pentru $50%$ din teste $N ≤ 1000$;
* *Atenţie!*: Bujorel recomandă tipuri de date pe $64$ de biţi pentru afişarea rezultatului.
 

* $... ≤ ... ≤ ...$

h2. Exemplu

table(example). |_. zlego.in |_. zlego.out |_. Explicaţie |
| 2
3
1 2 1
2 2 2
10
1 1 2 1 1 1 1 2 1 1
1 2 3 4 5 6 7 8 9 10
| 4
2
2
44
30
11
13
15
6
7
8
9
10
| În cel de-al doilea test, pentru zprefixul [1, 1] obţinem suma costurilor de frumusete ale apariţiilor acestuia
44 = 1+2+4+5+6+7+9+10. Pentru  [1, 2] avem 2+5+6+7+10, pentru [1, 3] avem 3+8, pentru [1, 4] avem 4+9, pentru [1, 5]
avem 5 + 10, pentru [1, 6] avem 6, pentru [1, 7] avem 7, pentru [1, 8] avem 8, pentru [1, 9] avem 9, iar pentru
[1, 10] avem 10.
|

table(example). |_. zlego.in |_. zlego.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="zlego") ==

7745