#P1433. 计算特殊递推数列的第N项

计算特殊递推数列的第N项

题目描述

在数学王国中,存在一种神秘的数列,它的前三个数字被封印在古老的石碑上:

  • 当x=1时,数字为2
  • 当x=2时,数字为3
  • 当x=3时,数字为5

从第4项开始,每个数字都遵循这样的法则:它等于前一个数字加上前前一个数字,再减去前前前一个数字。即: F(n) = F(n-1) + F(n-2) - F(n-3)

作为数学王国的探险家,你需要计算出这个数列的第n项,帮助解开石碑上的秘密。

输入格式

输入一个正整数n(4 ≤ n ≤ 10^5)

输出格式

输出只有一个整数F(n)

样例

5
8

提示

注意数列的递推规律