De fapt nu e majoritar

Ați vrut majoritar și ați primit majoritar fake. V-ați luat țeapă 😊

Și ce dacă mă cheamă Majoritar? Înseamnă că o să câștig alegerile.

Cerință

Se dă $n$ și un șir $a$ de $n$ numere întregi. Majoritar vrea să împartă șirul în trei părți nevide (cu cel puțin un element), astfel încât suma elementelor majoritare celor trei părți să fie maximă.

Definim elementul majoritar al unui șir $b$ ca fiind valoarea care apare de cele mai multe ori în $b$. Dacă există mai multe astfel de valori (care apar de la fel de multe ori), elementul majoritar va fi egal cu cea mai mare dintre ele.

Pentru mai multe detalii vedeți exemplele.

Date de intrare

Pe prima linie se va afla un număr întreg $n$, reprezentând numărul de elemente ale șirului $a$. Pe următoarea linie se vor afla $n$ întregi, reprezentând șirul $a$.

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, reprezentând suma maximă a elementelor majoritare care se poate obține dintr-o împărțire.

Restricții și precizări

• $3 \leq N \leq 2 \ 000$
• $1 \leq a_i \leq 1 \ 000 \ 000$
• Pentru $40$ de puncte, $1 \leq N \leq 500$

Exemplul 1

stdin

7
1 2 2 3 3 3 1

stdout

8

Explicație

Împărțirea este $1 \ 2 \ 2 \ | \ 3 \ | \ 3 \ 3 \ 1$. Rezultatul este $2 + 3 + 3 = 8$. Se poate demonstra că nu există o împărțire mai bună de atât.

Exemplul 2

stdin

6
4 4 5 5 5 6

stdout

16

Explicație

Împărțirea este $4 \ 4 \ 5 \ 5 \ | \ 5 \ | \ 6$. Rezultatul este $5 + 5 + 6 = 16$. Se poate demonstra că nu există o împărțire mai bună de atât.