## 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
```

Difficulty: introductory

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]

# precaclulate results
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]