std::vector<int> IterateOverQueries(const std::vector<int>& input_array) {
    std::vector<size_t> solved_first_subproblem;
    std::vector<size_t> solved_second_subproblem;

    solved_first_subproblem.resize(input_array.size());
    solved_second_subproblem.resize(input_array.size());

    solved_first_subproblem[input_array.size() - 1] = 1;
    solved_second_subproblem[input_array.size() - 1] = 1;
    for (int current_index = input_array.size() - 2; current_index >= 0;
         --current_index) {
        solved_first_subproblem[current_index] = 1;
        solved_second_subproblem[current_index] = 1;
        for (size_t previous_index = current_index + 1;
             previous_index < input_array.size(); ++previous_index) {
            if (input_array[previous_index] < input_array[current_index]) {
                solved_second_subproblem[current_index] =
                        std::max(solved_first_subproblem[previous_index] + 1,
                                 solved_second_subproblem[current_index]);
            }
            if (input_array[previous_index] > input_array[current_index]) {
                solved_first_subproblem[current_index] =
                        std::max(solved_second_subproblem[previous_index] + 1,
                                 solved_first_subproblem[current_index]);
            }
        }
    }

    size_t answerlength_f = 0;
    size_t answerlength_s = 0;
    int answerind_f = 0;
    int answerind_s = 0;
    for (size_t i = 0; i < solved_first_subproblem.size(); ++i) {
        if (answerlength_f < solved_first_subproblem[i]) {
            answerind_f = i;
            answerlength_f = solved_first_subproblem[i];
        }
    }
    for (size_t i = 0; i < solved_second_subproblem.size(); ++i) {
        if (answerlength_s < solved_second_subproblem[i]) {
            answerind_s = i;
            answerlength_s = solved_second_subproblem[i];
        }
    }
    std::vector<int> answer;
    answer.reserve(input_array.size());
    bool decide, ans_f, ans_s;
    ans_f = false;
    ans_s = false;
    size_t lenans;
    decide = false;
    if (answerlength_f > answerlength_s) {
        ans_f = true;
        lenans = answerlength_f;
        answer.push_back(answerind_f);
    } else if (answerlength_f < answerlength_s) {
        ans_s = true;
        lenans = answerlength_s;
        answer.push_back(answerind_s);
    } else {
        decide = true;
        lenans = answerlength_s;
        answer.push_back(answerind_s);
    }
    lenans -= 1;
    if (decide) {
        for (size_t currind = answerind_f; currind < input_array.size();++currind) {
            if (input_array[currind] > answer[0] && solved_first_subproblem[currind] == lenans) {
                answer.push_back(currind);
                ans_f = true;
                ans_s = false;
                lenans -= 1;
                break;
            }
            if (input_array[currind] < answer[0] && solved_second_subproblem[currind] == lenans) {
                answer.push_back(currind);
                ans_s = true;
                ans_f = false;
                lenans -= 1;
                break;
            }
        }
    }
    for (size_t currind = answer.back(); currind < input_array.size(); ++currind) {
        if (answer.size() == 1) {
            if (ans_f) {
                if (input_array[currind] > input_array[answer.back()] &&
                    solved_second_subproblem[currind] == lenans) {
                    answer.push_back(currind);
                    lenans -= 1;
                }
            } else if (ans_s) {
                if (input_array[currind] < input_array[answer.back()] &&
                    solved_first_subproblem[currind] == lenans) {
                    answer.push_back(currind);
                    lenans -= 1;
                }
            }
        } else {
            if (input_array[answer[answer.size() - 2]] >
                input_array[answer[answer.size() - 1]]) {
                if (input_array[currind] > input_array[answer.back()] &&
                    solved_second_subproblem[currind] == lenans) {
                    answer.push_back(currind);
                    lenans -= 1;
                }
            } else if (input_array[answer[answer.size() - 2]] <
                       input_array[answer[answer.size() - 1]]) {
                if (input_array[currind] < input_array[answer.back()] &&
                    solved_first_subproblem[currind] == lenans) {
                    answer.push_back(currind);
                    lenans -= 1;
                }
            }
        }
    }
    for (auto& x: answer) {
        x = input_array[x];
    }
    return answer;
}