La conexión perdida de Neru#12447
Neru estaba viendo videos en internet cuando su conexión desapareció de repente. Ahora está muy enojada y quiere restaurar la conexión de la forma más inestable posible.
La conexión consiste en celdas de señal consecutivas. La potencia de la -ésima celda es igual a p_k.
La inestabilidad de la conexión depende de las celdas vecinas. Formalmente, el valor de la conexión se define como
(p_1 \oplus p_2) + (p_2 \oplus p_3) + \ldots + (p_{n-1} \oplus p_n).
Para restaurar la conexión, Neru debe elegir exactamente dos posiciones iniciales y (1 \le i, j \le n-3). Para cada posición elegida, puede reordenar en cualquier orden las cuatro celdas consecutivas que empiezan en esa posición.
En otras palabras, Neru puede reordenar de forma independiente los elementos de los segmentos p[i..i+3] y p[j..j+3].
Los dos segmentos elegidos no deben intersectarse, es decir, |i-j| > 3.
Determina el máximo valor posible de la conexión después de elegir dos segmentos válidos y reordenar sus elementos de forma óptima.
La primera línea contiene un entero (8 \le n \le 2 \cdot 10^5) — el número de celdas de señal.
La segunda línea contiene enteros p_1, p_2, \ldots, p_n (0 \le p_i < 2^{30}) — las potencias de las celdas de señal.
Imprime un solo entero — el máximo valor posible de la conexión después de elegir dos segmentos válidos y reordenar sus elementos de forma óptima.
Ejemplo 1
Ejemplo 2
En el primer ejemplo, Neru puede elegir los segmentos y .
Después de reordenar los elementos, el arreglo puede convertirse en [1, 2, 4, 3, 5, 6, 8, 7].
El valor de la conexión es
(1 \oplus 2) + (2 \oplus 4) + (4 \oplus 3) + (3 \oplus 5) + (5 \oplus 6) + (6 \oplus 8) + (8 \oplus 7) = 54.
En el segundo ejemplo, un resultado óptimo es [5, 1, 12, 3, 10, 7, 9, 6, 15, 2], y el valor de la conexión es .
Subtarea ( puntos): n = 8.
Subtarea ( puntos): 8 \le n \le 40.
Subtarea ( puntos): 8 \le n \le 4000.
Subtarea ( puntos): 0 \le p_i \le 1 para todo 1 \le i \le n.
Subtarea ( puntos): Sin restricciones adicionales.