#include <iostream>

using namespace std;

struct Fraction
{
    int numerator;
    int denominator;
    Fraction* next;

    Fraction(int numerator, int denominator, Fraction* next)
    {
        this->numerator = numerator;
        this->denominator = denominator;
        this->next = next;
    }
    Fraction()
    {
        next = nullptr;
        numerator = 1;
        denominator = 1;
    }
};

void OutputFareySequence(Fraction* array)
{
    Fraction* current = array;
    while (current != nullptr)
    {
        cout << current->numerator << " / " << current->denominator << endl;
        current = current->next;
    }
}

void GetFareySequence(Fraction* array, int n)
{
    array[1] = Fraction(1, 1, nullptr);
    array[0] = Fraction(0, 1, &array[1]);
    int newFractionPosition = 2;
    for (int i = 2; i <= n; i++)
    {
        Fraction* current = array;
        while (current->next != NULL)
        {
            if (current->denominator + current->next->denominator == i)
            {
                int newFractionNumerator = current->numerator + current->next->numerator;
                int newFracTionDenominator = current->denominator + current->next->denominator;
                array[newFractionPosition] = Fraction(newFractionNumerator, newFracTionDenominator, current->next);
                current->next = &array[newFractionPosition++];
            }
            current = current->next;
        }
    }
}

int main()
{
    struct Fraction array[10000];
    int arraySize = sizeof(array) / sizeof(array[0]);
    int n;
    cout << "Enter n (array size "<< arraySize <<" elements)" << endl;
    cin >> n;
    GetFareySequence(array, n);
    OutputFareySequence(array);
}