public class Solution {
    public int Fibonacci(int n) {
        if(n==1 || n==2)
            return 1;
        int first  = 1;
        int second = 1;
        for(int i=0; i<(n+1)/2-1; i++){
            first = first+second;
            second = first+second;
        }
        return n%2==1?first:second;
    }
}