409393: GYM103496 F Funny Sequence

Alice has several long tests tomorrow, each worth at least 40% of her final grade in their respective subjects. So, naturally, she is procrastinating by watching videos on Youtube. She loves watching Numberphile videos, especially the ones that feature one of her mathematical idols, Neil Sloane. Sloane shows off tons of quirky integer sequences in his Numberphile appearances, so Alice decides to create her own cool sequence.

Let $$$a_n$$$ denote the $$$n$$$th term in the Alice sequence. Alice starts with the two terms $$$a_0 = 2$$$ and $$$a_1 = 3$$$. Then, Alice defines the sequence recursively, meaning each next entry in the sequence can be expressed in terms of the entries in the sequence that came before it (like in the Fibonacci sequence). For $$$n \geq 2$$$, Alice writes the formula $$$a_n = 2\ a_{n-1} - a_{n-2} + 2$$$.

The task is simple. Given $$$n$$$, find the value of $$$a_n$$$ in Alice's sequence. If you do it quickly enough, maybe Alice will still have time to study.

Input consists of a single line containing a single integer $$$n$$$.

Output a single line, containing the value of $$$a_n$$$.

$$$$$$\begin{align*}

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{30} & 0 \leq n \leq 10 \\ \hline 2 & \mathbf{15} & 0 \leq n \leq 100 \\ \hline 3 & \mathbf{15} & 0 \leq n \leq 10^4 \\ \hline 4 & \mathbf{10} & 0 \leq n \leq 10^5 \\ \hline 5 & \mathbf{30} & 0 \leq n \leq 3\times 10^9 \\ \hline \end{array}\\

\end{align*}$$$$$$

0

2

1

3

2

6

The values of $$$a_0$$$ and $$$a_1$$$ are $$$2$$$ and $$$3$$$, by definition. To get the value of $$$a_2$$$, we compute $$$a_2 = 2 \ a_1 - a_0 + 2 = 2 \times 3 - 2 + 2 = 6$$$.