Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

For an array $B$, while it has more than one element, you can apply an operation on it - you choose any two elements $x,y$  (they may be the same value, but they should have different indices), delete them, and add an element $g(x, y)$ instead. 

Here $g(x, y)$ denotes the highest set bit in $x \oplus y$, or $0$ if they are equal. In other words, $g(x, y) = \max 2^{k}$, such that $2^{k} ≤ (x \oplus y)$ for $x \neq y$, and $g(x,y)=0$ if $x = y$. For example, $g(1,1) = 0, g(1,2) = 2, g(2,4)=4, g(13,17)=16$.

Given an array $B$, we try to apply the operations repeatedly in such a way that when we are left with only one element at the end, that element is as small as possible. Let's denote this smallest possible value of the element at the end as $f(B)$.

You are given an array $A$ with $N$ elements, you need to find the sum of $f(A_{l \ldots r})$ among all subsegments $1 ≤ l ≤ r ≤ N$.

The answer may be large, so you need to find it modulo $998\,244\,353$.

------ Input: ------
The first line contains one integer $N$.
The second line contains $N$ integers $A_{1}, A_{2}, \ldots, A_{N}$.

------ Output: ------
In a single line, print the sum, modulo $998\,244\,353$.

------ Constraints  ------
$1 ≤ N ≤ 300\,000$
$0 ≤ A_{i} < 2^{30}$

------ Subtasks ------
10 points : $1 ≤ N ≤ 10$
10 points : $1 ≤ N ≤ 500$
10 points : $1 ≤ N ≤ 5000$
70 points : $1 ≤ N ≤ 300\,000$

----- Sample Input 1 ------ 
10  

0 1 2 3 4 5 6 7 8 9
----- Sample Output 1 ------ 
160

Difficulty: VERY_HARD
Tags: Bit manipulation

Constructive algorithms

Mathematics

Ad-hoc
Skill types: Bit manipulation

Starter code:

Solutions:
from itertools import combinations
import random

def dc(a, b):
	c = a ^ b
	c = int(2 ** (c.bit_length() - 1))
	return c

def cal2(a):
	a.sort()
	mp = int(2 ** (a[-1].bit_length() - 1))
	while len(a) > 1:
		p = 0
		if a[0] == mp and len(a) > 2:
			p = 1
		c = a[p] ^ a[-1]
		c = int(2 ** (c.bit_length() - 1))
		del a[-1]
		a[p] = c
		a.sort()
	return a[0]

def cal(a):
	la = len(a)
	a.sort()
	mp = int(2 ** (a[-1].bit_length() - 1))
	mc = 0
	for x in a:
		if x >= mp:
			mc += 1
	if la == 2:
		return dc(a[0], a[1])
	if la == 3:
		if mc == 1:
			return mp
		return min(dc(dc(a[0], a[1]), a[2]), dc(dc(a[2], a[1]), a[0]), dc(dc(a[0], a[2]), a[1]))
	if la == 4:
		if mc == 1:
			return mp
		if mc == 2:
			return 0
		if mc == 3:
			return mp
		if mc == 4:
			return min(dc(dc(dc(a[0], a[1]), a[2]), a[3]), dc(dc(dc(a[2], a[1]), a[0]), a[3]), dc(dc(dc(a[0], a[2]), a[1]), a[3]), dc(dc(a[0], a[1]), dc(a[2], a[3])), dc(dc(a[0], a[2]), dc(a[1], a[3])), dc(dc(a[0], a[3]), dc(a[2], a[1])), dc(dc(dc(a[3], a[1]), a[2]), a[0]), dc(dc(dc(a[3], a[1]), a[0]), a[2]), dc(dc(dc(a[3], a[2]), a[0]), a[1]))
	if la == 5:
		if mc == 1:
			return mp
		if mc == 2:
			return 0
		if mc == 3:
			return mp
		if mc == 4:
			return 0
		if mc == 5:
			return mp
n = int(input())
a = list(map(int, input().split()))
if True:
	result = 0
	res1 = result
	result = 0
	ph = {}
	ap = [0 for _ in range(n)]
	for i in range(n):
		ap[i] = int(2 ** (a[i].bit_length() - 1))
	for i in range(n):
		result += a[i]
	for i in range(n):
		for j in range(max(i - 4, 0), i):
			v1 = cal(ap[j:i + 1])
			v2 = cal(a[j:i + 1])
			if v1 != v2:
				result += abs(v1 - v2)
	for i in range(n):
		p = ap[i]
		phn = {}
		s = 0
		for (k, v) in ph.items():
			(lp, le) = k
			if p < lp:
				phn[k] = v
			if p > lp:
				s += v
		if (p, 0) in ph:
			phn[p, 1] = ph[p, 0] + 1 + s
		else:
			phn[p, 1] = 1 + s
		if (p, 1) in ph:
			phn[p, 0] = ph[p, 1]
		ph = phn
		tr = 0
		for (k, v) in ph.items():
			(lp, le) = k
			if le == 1:
				if lp == p:
					tr += lp * (v - 1)
				else:
					tr += lp * v
		result += tr
		result = result % 998244353
	print(result)


import sys
import math
from collections import defaultdict, Counter
input = sys.stdin.readline

def print(x):
	sys.stdout.write(str(x) + '\n')

def find(a, b, c):
	cur = a ^ b
	if cur == 0:
		now = 0
	else:
		now = pow(2, int(math.log2(cur)))
	if now == c:
		return -1
	cur = now ^ c
	mi = int(math.log2(cur))
	cur = a ^ c
	if cur == 0:
		now = 0
	else:
		now = pow(2, int(math.log2(cur)))
	if now == b:
		return -1
	cur = now ^ b
	mi = min(mi, int(math.log2(cur)))
	cur = c ^ b
	if cur == 0:
		now = 0
	else:
		now = pow(2, int(math.log2(cur)))
	if now == a:
		return -1
	cur = now ^ a
	mi = min(mi, int(math.log2(cur)))
	return mi
mod = 998244353
n = int(input())
a = list(map(int, input().split()))
l = [0] * n
f = [0] * 32
for i in range(31):
	f[i] = 1 << i
pre = [0] * n
ind = [[0, 0]] * n
ans = a[0] % mod
if a[0] == 0:
	l[0] = -1
	pre[0] = 0
else:
	b = math.log2(a[0])
	l[0] = int(b)
	pre[0] = f[l[0]]
ind[0] = [l[0], 0]
top = 0
for i in range(1, n):
	ans = (ans + a[i]) % mod
	if a[i] == 0:
		l[i] = -1
	else:
		b = math.log2(a[i])
		l[i] = int(b)
	while l[i] > ind[top][0]:
		top -= 1
		if top == -1:
			break
	if top == -1:
		pre[i] = f[l[i]] * i
		ans = (ans + pre[i]) % mod
		pre[i] = (pre[i] + f[l[i]]) % mod
	else:
		pre[i] = f[l[i]] * (i - ind[top][1] - 1)
		ans = (ans + pre[i]) % mod
		pre[i] = (pre[i] + f[l[i]]) % mod
		if l[i] == ind[top][0]:
			top1 = top - 1
			if top1 != -1:
				pre[i] = (pre[i] + pre[ind[top1][1]]) % mod
				ans = (ans + pre[ind[top1][1]]) % mod
		else:
			ans = (ans + pre[ind[top][1]]) % mod
			pre[i] = (pre[i] + pre[ind[top][1]]) % mod
	top += 1
	ind[top] = [l[i], i]
for i in range(n - 1):
	d = defaultdict(int)
	ma = max(l[i], l[i + 1])
	d[l[i]] = 1
	d[l[i + 1]] += 1
	if l[i] == l[i + 1]:
		cur = a[i] ^ a[i + 1]
		if cur != 0:
			b = int(math.log2(cur))
			ans = (ans + f[b]) % mod
	for j in range(i + 2, min(n, i + 4)):
		d[l[j]] += 1
		ma = max(ma, l[j])
		if d[ma] & 1:
			pass
		elif d[ma] == 2 and j == i + 2:
			cur = find(a[i], a[i + 1], a[i + 2])
			ans = (ans + f[cur]) % mod
		elif d[ma] == 4:
			p = a[i] ^ a[i + 1]
			if p == 0:
				now = 0
			else:
				now = f[int(math.log2(p))]
			cur = find(now, a[i + 2], a[i + 3])
			p = a[i] ^ a[i + 2]
			if p == 0:
				now = 0
			else:
				now = f[int(math.log2(p))]
			cur = min(cur, find(now, a[i + 1], a[i + 3]))
			p = a[i] ^ a[i + 3]
			if p == 0:
				now = 0
			else:
				now = f[int(math.log2(p))]
			cur = min(cur, find(now, a[i + 1], a[i + 2]))
			p = a[i + 1] ^ a[i + 2]
			if p == 0:
				now = 0
			else:
				now = f[int(math.log2(p))]
			cur = min(cur, find(now, a[i], a[i + 3]))
			p = a[i + 1] ^ a[i + 3]
			if p == 0:
				now = 0
			else:
				now = f[int(math.log2(p))]
			cur = min(cur, find(now, a[i], a[i + 2]))
			p = a[i + 3] ^ a[i + 2]
			if p == 0:
				now = 0
			else:
				now = f[int(math.log2(p))]
			cur = min(cur, find(now, a[i + 1], a[i]))
			ans = (ans + f[cur]) % mod
print(ans)