#include <iostream>
#include <vector>
#include <algorithm>

struct Ant {
    int position;
    int direction; // -1 for left, 1 for right
};

int timeUntilAllFall(int plankSize, std::vector<int> left, std::vector<int> right) {
    std::vector<Ant> ants;

    // Initialize ants
    for (int pos : left) ants.push_back({pos, -1});
    for (int pos : right) ants.push_back({pos, 1});

    int time = 0;

    while (!ants.empty()) {
        time++;

        // Move all ants
        for (auto& ant : ants) {
            ant.position += ant.direction;
        }

        // Handle collisions — if two ants are on the same position, switch direction
        for (int i = 0; i < ants.size(); ++i) {
            for (int j = i + 1; j < ants.size(); ++j) {
                if (ants[i].position == ants[j].position) {
                    ants[i].direction *= -1;
                    ants[j].direction *= -1;
                }
            }
        }

        // Remove ants that fall off the plank
        ants.erase(std::remove_if(ants.begin(), ants.end(),
                                  [plankSize](const Ant& ant) {
                                      return ant.position < 0 || ant.position > plankSize;
                                  }),
                   ants.end());
    }

    return time;
}

int main() {
    int plankSize = 10;
    std::vector<int> left = {4, 7};
    std::vector<int> right = {2, 5};

    int totalTime = timeUntilAllFall(plankSize, left, right);
    std::cout << "Time until all ants fall off: " << totalTime << " seconds\n";

    return 0;
}