class Solution {
public:
    int Fibonacci(int n) {
        int fib[3] = {0, 1, 1};
        if(n <= 2) return fib[n];
        for(int i = 0; i < n - 2;i++){
            fib[0] = fib[1];
            fib[1] = fib[2];
            fib[2] = fib[0] + fib[1];
        }
        return fib[2];
    }
};