## Task

Find the sum of the first `n` elements in the Recamán Sequence.

Input range:

```python
1000 tests
0 <= n <= 2,500,000
```

___

## Sequence

The sequence is formed using the next formula:
* We start with `0`
* At each step `i`, we subtract `i` from the previous number
* If the result is not negative, and not yet present in the sequence, it becomes the `i`th element of the sequence
* Otherwise the `i`th element of the sequence will be previous number plus `i`

The beginning of the sequence is `[0, 1, 3, 6, 2, ...]` because:  
0) `0` <- we start with `0`  
1) `1` <- `0 - 1` is negative, hence we choose `0 + 1`  
2) `3` <- `1 - 2` is negative, hence we choose `1 + 2`  
3) `6` <-`3 - 3` is not negative, but we already have a `0` in the sequence, hence we choose `3 + 3`  
4) `2` <- `6 - 4` is positive, and is not present in the sequence yet, so we go for it

___

## Examples

```
rec(0) == 0
rec(1) == 0
rec(2) == 1
rec(3) == 4
rec(4) == 10
rec(5) == 12
```

Source: codewars | Difficulty: EASY

Starter code: def rec(x):
	

Solutions:
(S, SS, SUM) = ([0], {0}, [0])

def rec(n):
	while len(S) <= n:
		v = S[-1] - len(S)
		if v <= 0 or v in SS:
			v += 2 * len(S)
		S.append(v)
		SS.add(v)
		SUM.append(SUM[-1] + v)
	return SUM[n - 1]


LIMIT = 2500000
RECA_SUM = [0, 0]
seen = {0}
last = 0
total = 0
for n in range(1, LIMIT):
	new = last - n
	if new < 0 or new in seen:
		new = last + n
	seen.add(new)
	total += new
	RECA_SUM.append(total)
	last = new
del seen

def rec(x):
	return RECA_SUM[x]


(s, seq, sums) = ({0}, [0], [0])
for i in range(25 * 10 ** 5 + 1):
	x = seq[-1] - i
	if x < 0 or x in s:
		x += 2 * i
	s.add(x)
	seq.append(x)
	sums.append(x + sums[-1])
rec = sums.__getitem__


all_sums = {}

def helper():
	all_sums[0] = 0
	(rec, suma) = (0, 0)
	made = {0}
	for i in range(1, 2500000):
		cur = rec - i
		if cur < 0 or cur in made:
			cur = rec + i
		suma += cur
		made.add(cur)
		rec = cur
		all_sums[i] = suma
	return True

def rec(x):
	if not all_sums:
		helper()
	return all_sums[x - 1] if x >= 1 else 0


(____, _____) = ({0}, [0])
___ = [0, 0]

def rec(_):
	for _______ in range(len(_____), _ + 1):
		________ = _____[-1] - _______
		if not (________ >= 0 and ________ not in ____):
			________ += _______ + _______
		____.add(________)
		_____.append(________)
		___.append(___[-1] + ________)
	return ___[_]


(cache2, cache, seq) = ({0: 0}, {0: 0, 1: 0}, {0})

def rec(n):
	if n in cache2:
		return cache[n]
	i = max(cache2)
	r = cache2[i]
	for i in range(i + 1, n):
		cache2[i] = r = [r - i, r + i][(r - i < 0) | (r - i in seq)]
		seq.add(r)
		cache[i + 1] = cache[i] + r
	return cache[n]


SEEN = {0}
REC = [0]
SUM = [0, 0]

def rec(n):
	for i in range(len(REC), n + 1):
		k = REC[-1] - i
		if not (k >= 0 and k not in SEEN):
			k += i + i
		SEEN.add(k)
		REC.append(k)
		SUM.append(SUM[-1] + k)
	return SUM[n]


R = [0, 0]
s = 0
p = 0
S = {0}
for i in range(1, 2500000):
	x = p - i
	if x < 0 or x in S:
		x = p + i
	S |= {x}
	s += x
	p = x
	R += [s]

def rec(x):
	return R[x]