#include <iostream>
#include <vector>
#include <deque>
#include <map>

using namespace std;


class SequenceSolver
{
public:
    SequenceSolver(vector<int>& sequence);

    int getCount() { return maxCount_; }

    vector<int> getSequence();

private:
    // находит все числа-кандидаты для построения последовательностей
    void buildNumbers(vector<int>& sequence);

    // прекращает построение/проверку активной последовательности
    void terminateCurrentSequence();

    // делит последовательность на две по элементу с индексом position
    size_t splitSequence(deque<int>& sequence, size_t position);

    // начинает построение новой последовательности
    void beginSequence(size_t& index, int number);

    // начинает проверку существующей последовательности
    void beginSequenceCheck(size_t index, size_t position);

private:
    static const size_t NONE = (size_t)(-1);

    // числа-кандидаты для построения последовательностей
    // значение - (индекс последовательности, позиция в последовательности)
    map<int, pair<size_t, size_t>> numbers_;

    // последовательности-кандидаты
    vector<deque<int>> sequences_;

    // индекс и текущая позиция активной последовательности
    // (которая строится или проверяется в данный момент)
    size_t activeIndex_;
    size_t activePosition_;

    // true, если активная последовательность встретилась впервые
    bool activeNew_;

    // сколько раз встречается искомая последовательность
    int maxCount_;
};


SequenceSolver::SequenceSolver(vector<int>& sequence) : maxCount_(0), activeIndex_(NONE)
{
    buildNumbers(sequence);

    for (size_t i = 0; i < sequence.size(); i++)
    {
        auto it = numbers_.find(sequence[i]);
        if (it == numbers_.end())
        {
            terminateCurrentSequence();
        }
        else
        {
            if (activeIndex_ == NONE) // нет активной последовательности
            {
                if (it->second.first == NONE)
                {
                    beginSequence(it->second.first, it->first);
                }
                else
                {
                    beginSequenceCheck(it->second.first, it->second.second);
                }
            }
            else if (activeNew_) // есть новая активная последовательность
            {
                if (it->second.first == NONE)
                {
                    // продолжаем новую активную последовательность
                    it->second.first = activeIndex_;
                    it->second.second = activePosition_;
                    sequences_[activeIndex_].push_back(it->first);
                    activePosition_ += 1;
                }
                else
                {
                    // прерываем новую активную последовательность
                    // и начинаем проверку старой активной последовательности
                    terminateCurrentSequence();
                    beginSequenceCheck(it->second.first, it->second.second);
                }
            }
            else // есть старая активная последовательность
            {
                if (it->second.first == NONE)
                {
                    // прерываем старую активную последовательность
                    // и начинаем новую активную последовательность
                    terminateCurrentSequence();
                    beginSequence(it->second.first, it->first);
                }
                else if (it->second.first == activeIndex_ && it->second.second == activePosition_)
                {
                    // продолжаем проверку старой активной последовательности
                    activePosition_ += 1;
                    if (activePosition_ == sequences_[activeIndex_].size())
                    {
                        activeIndex_ = NONE;
                    }
                }
                else
                {
                    // прерываем старую активную последовательность
                    // и начинаем проверку другой старой активной последовательности
                    terminateCurrentSequence();

                    // обработка случая, когда число находится в этой же последовательности но на более
                    // далёкой позиции, например:  [ 1 2 3 4 5 ] и [ 1 2 5 ]
                    if (numbers_.find(sequence[i]) == numbers_.end())
                    {
                        activeIndex_ = NONE;
                    }
                    else
                    {
                        beginSequenceCheck(it->second.first, it->second.second);
                    }
                }
            }
        }
    }
}

vector<int> SequenceSolver::getSequence()
{
    size_t max = 0;
    for (size_t i = 1; i < sequences_.size(); i++)
    {
        if (sequences_[i].size() > sequences_[max].size())
        {
            max = i;
        }
    }

    return vector<int>(sequences_[max].begin(), sequences_[max].end());
}

void SequenceSolver::buildNumbers(vector<int>& sequence)
{
    map<int, int> counts;
    for (size_t i = 0; i < sequence.size(); i++)
    {
        counts[sequence[i]]++;
    }

    maxCount_ = 0;
    for (auto it = counts.begin(); it != counts.end(); ++it)
    {
        maxCount_ = it->second > maxCount_ ? it->second : maxCount_;
    }

    for (auto it = counts.begin(); it != counts.end(); ++it)
    {
        if (it->second == maxCount_)
        {
            numbers_[it->first] = make_pair(NONE, 0);
        }
    }
}

void SequenceSolver::terminateCurrentSequence()
{
    if (activeIndex_ != NONE && !activeNew_)
    {
        splitSequence(sequences_[activeIndex_], activePosition_);
    }
    activeIndex_ = NONE;
}

size_t SequenceSolver::splitSequence(deque<int>& sequence, size_t position)
{
    deque<int> temp(sequence.begin() + position, sequence.end());
    sequence.erase(sequence.begin() + position, sequence.end());
    size_t index = NONE;
    if (temp.size() > 0)
    {
        index = sequences_.size();
        for (size_t i = 0; i < temp.size(); i++)
        {
            numbers_[temp[i]] = make_pair(index, i);
        }
        sequences_.push_back(temp);
    }
    return index;
}

void SequenceSolver::beginSequence(size_t& index, int number)
{
    index = sequences_.size();
    sequences_.push_back(deque<int>());
    sequences_.back().push_back(number);
    activeIndex_ = index;
    activePosition_ = 1;
    activeNew_ = true;
}

void SequenceSolver::beginSequenceCheck(size_t index, size_t position)
{
    activeIndex_ = splitSequence(sequences_[index], position);
    activePosition_ = 1;
    activeNew_ = false;
    if (activePosition_ == sequences_[activeIndex_].size())
    {
        activeIndex_ = NONE;
    }
}

int main()
{
    int arr[] = { 1, 2, 3, 4, 0, 4, 2, 3, 2, 3 };
    
    SequenceSolver sol(vector<int>(arr, arr + sizeof(arr) / sizeof(int)));
    vector<int> ans = sol.getSequence();

    cout << "N = " << sol.getCount() << endl;
    cout << ans[0];
    for (size_t i = 1; i < ans.size(); i++)
    {
        cout << " " << ans[i];
    }
    cout << endl;
    return 0;
}