#include<iostream>
#include"partition.h"
#include<vector>
using namespace std;
int dp[100001];
int rebuild[100001];
bool used[100001];
void rebuilding(int cur)
{
    used[cur] = true;
    if(rebuild[cur] != -1) rebuilding(rebuild[cur]);
}
vector<int> solve(vector<int> A)
{
    int sum = 0;
    int N = A.size();
    for(int i = 0; i < N; i++) sum+=A[i];
    for(int i = 0; i < N; i++)
    {
        int cur = sum/2-A[i];
        rebuild[i] = -1;
        for(int j = i-1; j >= 0; j--)
        {
            if(abs(cur) > abs(dp[j] - A[i]))
            {
                if(abs(dp[j]-A[i]) == 0 && sum%2 != 0) continue;
                cur = dp[j] - A[i];
                rebuild[i] = j;
            }
            if(abs(cur) == abs(dp[j] - A[i]) && dp[j] - A[i] <= 0)
            {
                cur = dp[j] - A[i];
                rebuild[i] = j;
            }
        }
        dp[i] = cur;
    }
    int ans = 1e9;
    int pos = -1;
    for(int i = 0; i < N; i++)
    {
        if(ans > abs(dp[i]))
        {
            if (dp[i] == 0 && sum%2 != 0) continue;
            pos = i;
            ans = abs(dp[i]);
        }
    }
    rebuilding(pos);
    vector<int> answer;
    for(int i = 0; i < N; i++)
    {
        if(used[i]) answer.push_back(i);
    }
    for(int i = 0; i < N; i++)
    {
        if(!used[i]) answer.push_back(i);
    }
    return answer;
}
