Зниклий інтернет Неру#12447

Зниклий інтернет Неру

3 секунди

256 мегабайтів

Складна

Неру дивилася відео в інтернеті, коли з'єднання раптово зникло. Тепер вона дуже зла і хоче відновити інтернет-з'єднання так, щоб воно стало якомога нестабільнішим.

З'єднання складається з $n$ послідовних сигнальних комірок. Потужність $k$ -ї комірки дорівнює $p_{k}$ p_k.

Нестабільність з'єднання залежить від сусідніх комірок. Формально значення з'єднання визначається як

$(p_{1} \oplus p_{2}) + (p_{2} \oplus p_{3}) + \dots + (p_{n - 1} \oplus p_{n})$ (p_1 \oplus p_2) + (p_2 \oplus p_3) + \ldots + (p_{n-1} \oplus p_n).

Щоб відновити з'єднання, Неру повинна обрати рівно дві початкові позиції $i$ та $j$ $(1 \leq i, j \leq n - 3)$ (1 \le i, j \le n-3). Для кожної обраної позиції вона може переставити чотири послідовні комірки, що починаються з цієї позиції, у довільному порядку.

Іншими словами, Неру може незалежно переставити елементи відрізків $p [i .. i + 3]$ p[i..i+3] та $p [j .. j + 3]$ p[j..j+3].

Два обрані відрізки не повинні перетинатися, тобто $∣ i - j ∣ > 3$ |i-j| > 3.

Визначте максимальне можливе значення з'єднання після вибору двох коректних відрізків та оптимального переставлення їхніх елементів.

Вхідні дані

Перший рядок містить одне ціле число $n$ $(8 \leq n \leq 2 \cdot 1 0^{5})$ (8 \le n \le 2 \cdot 10^5) — кількість сигнальних комірок.

Другий рядок містить $n$ цілих чисел $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n $(0 \leq p_{i} < 2^{30})$ (0 \le p_i < 2^{30}) — потужності сигнальних комірок.

Вихідні дані

Виведіть одне ціле число — максимальне можливе значення з'єднання після вибору двох коректних відрізків та оптимального переставлення їхніх елементів.

Приклади

Приклад 1

Приклад 2

Примітка

У першому прикладі Неру може обрати відрізки $p [1..4]$ та $p [5..8]$ .

Після переставлення елементів масив може стати $[1, 2, 4, 3, 5, 6, 8, 7]$ [1, 2, 4, 3, 5, 6, 8, 7].

Значення з'єднання дорівнює

$(1 \oplus 2) + (2 \oplus 4) + (4 \oplus 3) + (3 \oplus 5) + (5 \oplus 6) + (6 \oplus 8) + (8 \oplus 7) = 54$ (1 \oplus 2) + (2 \oplus 4) + (4 \oplus 3) + (3 \oplus 5) + (5 \oplus 6) + (6 \oplus 8) + (8 \oplus 7) = 54.

У другому прикладі один з оптимальних результатів — $[5, 1, 12, 3, 10, 7, 9, 6, 15, 2]$ [5, 1, 12, 3, 10, 7, 9, 6, 15, 2], а значення з'єднання дорівнює $105$ .

Оцінювання

Підзадача $1$ ( $10$ балів): $n = 8$ n = 8.
Підзадача $2$ ( $30$ балів): $8 \leq n \leq 40$ 8 \le n \le 40.
Підзадача $3$ ( $40$ балів): $8 \leq n \leq 4000$ 8 \le n \le 4000.
Підзадача $4$ ( $40$ балів): $0 \leq p_{i} \leq 1$ 0 \le p_i \le 1 для всіх $1 \leq i \leq n$ 1 \le i \le n.
Підзадача $5$ ( $80$ балів): Без додаткових обмежень.