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