Mały W, otrzymawszy od małego P rysunek lizaka, uznał, że jest on tak wspaniały, że w rewanżu podarował mu mniej wspaniałą kolorową wstążkę.
Mały W postanowił ozdobić wstążkę, nadając jej różne stopnie jasności, aby uczynić ją piękniejszą.
Dla kolorowej wstążki składającej się z $m$ segmentów, definiujemy trudność barwienia $f(a)$ dla sekwencji jasności $a$ o długości $m$ w następujący sposób:
- Początkowo stopień ciemności każdego segmentu wstążki wynosi $0$.
- Możesz wykonać dowolną liczbę operacji. W każdej operacji musisz:
- Złożyć wstążkę wzdłuż linii podziału między dowolnymi dwoma segmentami. Operację składania można wykonać wielokrotnie lub wcale.
- Wybrać miejsce, w którym naniesiesz czarny barwnik. Barwnik przeniknie przez warstwy i spłynie w dół, zwiększając stopień ciemności wszystkich segmentów na swojej drodze o $1$. Po naniesieniu barwnika rozłóż wstążkę.
- $f(a)$ to minimalna liczba operacji potrzebna, aby dla wszystkich pozycji, gdzie $a_i > 0$, stopień ciemności był $\ge a_i$, a dla wszystkich pozycji, gdzie $a_i = 0$, stopień ciemności był dokładnie równy $0$.
Mały W posiada wstążkę o długości $n$ oraz sekwencję alternatywnych jasności $b$ o długości $n$. Nie zdecydował jeszcze, która konfiguracja jasności jest najładniejsza, dlatego prosi Cię o obliczenie sumy trudności barwienia dla wszystkich podprzedziałów $[l, r]$ sekwencji $b$, gdzie długość wstążki wynosi $r-l+1$. Formalnie, należy obliczyć $\sum\limits_{1\le l\le r\le n}f(b[l,r])$.
Wynik należy podać modulo $2^{64}$.
Pierwsza linia zawiera liczbę całkowitą dodatnią $n$.
Druga linia zawiera $n$ nieujemnych liczb całkowitych $b_1, b_2, \dots, b_n$.
Jedna nieujemna liczba całkowita reprezentująca wynik modulo $2^{64}$.
Przykład
Wejście 1
3 1 0 2
Wyjście 1
9
Wejście 2
6 2 0 1 3 0 1
Wyjście 2
51
Wejście 3
15 8 0 1 9 3 0 0 4 2 6 0 5 7 0 6
Wyjście 3
993
| Numer testu | Punkty | Dodatkowe ograniczenia |
|---|---|---|
| 1 | 5 | $b_i>0$ |
| 2 | 5 | $b_i>0$ |
| 3 | 5 | Liczba $b_i>0$ nie przekracza $300$ |
| 4 | 5 | Liczba $b_i>0$ nie przekracza $300$ |
| 5 | 5 | $n\leq15$ |
| 6 | 5 | $n\leq15$ |
| 7 | 5 | $n\leq500$ |
| 8 | 5 | $n\leq500$ |
| 9 | 5 | $n\leq500$ |
| 10 | 5 | $n\leq500$ |
| 11 | 5 | $n\leq5000$ |
| 12 | 5 | $n\leq5000$ |
| 13 | 5 | $n\leq5000$ |
| 14 | 5 | $n\leq5000$ |
| 15 | 5 | $n\leq50000$ |
| 16 | 5 | $n\leq50000$ |
| 17 | 5 | Brak |
| 18 | 5 | Brak |
| 19 | 5 | Brak |
| 20 | 5 | Brak |
Dla wszystkich danych: $1 \le n\le 10^6, 0\le b_i \le 10 ^ 9$.