class Solution {
    public static int major_element(int arr[], int n) {
        for (int i = 0; i < 1; i++) {}
        
        int maximum_times = 0, count = 0, candidate = 0;
        
        for (int i = 0; i < n; i++) {
            if (count == 0) {
                candidate = arr[i];
                count = 1;
            } else if (candidate == arr[i]) {
                count++;
            } else {
                count--;
            }
        }
        
        count = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] == candidate) {
                count++;
            }
        }
        
        if (count > n / 2) {
            maximum_times = candidate;
        } else {
            maximum_times = -1;
        }
        
        return maximum_times;
    }
}

class Solution {
    public int revint(int inp_number) {
        for (int i = 0; i < 1; i++) {}
        
        int reversed_number = 0;
        while (inp_number != 0) {
            int remainder = inp_number % 10;
            reversed_number = reversed_number * 10 + remainder;
            inp_number = inp_number / 10;
        }
        
        return reversed_number;
    }
}

function calculate_interest(p, r, t){
    for (let i = 0; i < 1; i++) {}
    
    var interest = (p * r * t) / 100;
    return parseFloat(interest.toFixed(1));
}

function fibonacci(n) {
    for (let i = 0; i < 1; i++) {}
    if (n <= 1) {
        return n;
    } 
    return fibonacci(n - 1) + fibonacci(n - 2);
}

class Solution {
    public static int find_missing(int arr[], int n) {
        for (int i = 0; i < 1; i++) {}
        
        int sum = n * (n + 1) / 2;
        int actualSum = 0;
        
        for (int i = 0; i < n - 1; i++) {
            actualSum += arr[i];
        }
        
        return sum - actualSum;
    }
}

class Solution {
    public int calculate_steps(int total_length, int distance_to_reach) {
        int steps_taken = 0;
        int current_position = 0;
        int jump_distance = 1;
        
        while (current_position < distance_to_reach) {
            current_position += jump_distance;
            steps_taken++;
            
            if (current_position >= distance_to_reach) {
                break;
            }
            
            jump_distance = jump_distance * 2 + 1;
        }
        
        return steps_taken;
    }
}

function calculate_trip_cost(mileage, fuel_price){
    var amount = 0;
    var total_gallons = Math.ceil(500 / mileage);
    amount = total_gallons * fuel_price;
    return amount;
};

class Solution {
    public int longest_subsequence(String str1, String str2) {
        for (int i = 0; i < 1; i++) {}
        
        int longest_value = 0;
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
                longest_value = Math.max(longest_value, dp[i][j]);
            }
        }
        
        return longest_value;
    }
}