#pragma comment(linker, "/STACK:16777216")
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <stack>
#include <unordered_set>
using namespace std;
vector<int> d, t;
const int inf = 1e4 + 1;
int dp[10000][10000][2];
int main() {
int n = 10000;
d.resize(n);
t.resize(n);
for (int i = 0; i < n; ++i) {
d[i] = t[i] = i + 1;
}
int temp, i, j;
for(int diag = 1; diag < n; ++diag){
for(int k = 0; k < n - diag; ++k){
i = k;
j = k + diag;
temp = min(dp[i][j - 1][0] + d[j] - d[i], dp[i][j - 1][1] + d[j] - d[j - 1]);
if(temp > t[j]){
temp = inf;
}
dp[i][j][1] = temp;
temp = min(dp[i + 1][j][1] + d[j] - d[i], dp[i + 1][j][0] + d[i + 1] - d[i]);
if(temp > t[i]){
temp = inf;
}
dp[i][j][0] = temp;
}
}
temp = min(dp[0][n - 1][0], dp[0][n - 1][1]);
if(temp != inf){
cout << temp << "\n";
}
else{
cout << "No solution\n";
}
return 0;
}
I3ByYWdtYSBjb21tZW50KGxpbmtlciwgIi9TVEFDSzoxNjc3NzIxNiIpCgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxmc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxjc3RyaW5nPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDx1bm9yZGVyZWRfc2V0PgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZlY3RvcjxpbnQ+IGQsIHQ7CmNvbnN0IGludCBpbmYgPSAxZTQgKyAxOwppbnQgZHBbMTAwMDBdWzEwMDAwXVsyXTsKCmludCBtYWluKCkgewogICAgaW50IG4gPSAxMDAwMDsKCiAgICBkLnJlc2l6ZShuKTsKICAgIHQucmVzaXplKG4pOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyArK2kpIHsKICAgICAgICBkW2ldID0gdFtpXSA9IGkgKyAxOwogICAgfQoKICAgIGludCB0ZW1wLCBpLCBqOwoKICAgIGZvcihpbnQgZGlhZyA9IDE7IGRpYWcgPCBuOyArK2RpYWcpewogICAgICAgIGZvcihpbnQgayA9IDA7IGsgPCBuIC0gZGlhZzsgKytrKXsKICAgICAgICAgICAgaSA9IGs7CiAgICAgICAgICAgIGogPSBrICsgZGlhZzsKCiAgICAgICAgICAgIHRlbXAgPSBtaW4oZHBbaV1baiAtIDFdWzBdICsgZFtqXSAtIGRbaV0sIGRwW2ldW2ogLSAxXVsxXSArIGRbal0gLSBkW2ogLSAxXSk7CiAgICAgICAgICAgIGlmKHRlbXAgPiB0W2pdKXsKICAgICAgICAgICAgICAgIHRlbXAgPSBpbmY7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZHBbaV1bal1bMV0gPSB0ZW1wOwoKICAgICAgICAgICAgdGVtcCA9IG1pbihkcFtpICsgMV1bal1bMV0gKyBkW2pdIC0gZFtpXSwgZHBbaSArIDFdW2pdWzBdICsgZFtpICsgMV0gLSBkW2ldKTsKICAgICAgICAgICAgaWYodGVtcCA+IHRbaV0pewogICAgICAgICAgICAgICAgdGVtcCA9IGluZjsKICAgICAgICAgICAgfQogICAgICAgICAgICBkcFtpXVtqXVswXSA9IHRlbXA7CiAgICAgICAgfQogICAgfQoKICAgIHRlbXAgPSBtaW4oZHBbMF1bbiAtIDFdWzBdLCBkcFswXVtuIC0gMV1bMV0pOwogICAgaWYodGVtcCAhPSBpbmYpewogICAgICAgIGNvdXQgPDwgdGVtcCA8PCAiXG4iOwogICAgfQogICAgZWxzZXsKICAgICAgICBjb3V0IDw8ICJObyBzb2x1dGlvblxuIjsKICAgIH0KICAgIAogICAgcmV0dXJuIDA7Cn0=