#include #include #define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) using namespace atcoder; using namespace std; typedef long long ll; template struct AllPairOperationSum { // https://shakayami.hatenablog.com/entry/2021/01/01/044946 // Σ op(a[i], a[j]) (i < j) ll n; vector a; AllPairOperationSum() {} AllPairOperationSum(vector a) : a(a), n(a.size()) {} S add() { // A + B // O(N) S ret = 0; rep(i, 0, n) ret += a[i]; ret *= (n - 1); return ret; } S sub() { // A - B // O(N) S ret = 0; rep(i, 0, n) ret += (S)(n - 1 - i * 2) * a[i]; return ret; } S mul() { // A * B // O(N) S ret = 0; vector s(n); s[0] = a[0]; rep(i, 1, n) { s[i] = s[i - 1] + a[i]; ret += s[i - 1] * a[i]; } return ret; } S div() { // A / B (有理数mod) // O(N log maxA) S ret = 0; vector invs(n); reverse(a.begin(), a.end()); invs[0] = (S)1 / a[0]; rep(i, 1, n) invs[i] = invs[i - 1] + (S)1 / a[i]; rep(i, 1, n) ret += invs[i - 1] * a[i]; reverse(a.begin(), a.end()); return ret; } T floor() { // floor(A / B) // O(N √maxA log maxA) T maxa = *max_element(a.begin(), a.end()); T sqrtmaxa = sqrt(maxa); vector v(sqrtmaxa, 0); fenwick_tree ft(maxa + 1); T ret = 0; rep(i, 0, n) { if (a[i] < sqrtmaxa) { ret += v[a[i]]; } else { for (T k = 0; k < maxa + 1; k += a[i]) { ret += (k / a[i]) * ft.sum(k, std::min(k + a[i], maxa + 1)); } } ft.add(a[i], 1); for (T j = 1; j < sqrtmaxa; j++) { v[j] += a[i] / j; } } return ret; } T mod() { // A % B // O(N √maxA log maxA) T maxa = *max_element(a.begin(), a.end()); T sqrtmaxa = sqrt(maxa); vector v(sqrtmaxa, 0); fenwick_tree ft(maxa + 1); T ret = 0; rep(i, 0, n) { if (a[i] < sqrtmaxa) { ret += v[a[i]] * a[i]; } else { for (T k = 0; k < maxa + 1; k += a[i]) { ret += (k / a[i]) * ft.sum(k, std::min(k + a[i], maxa + 1)) * a[i]; } } ft.add(a[i], 1); for (T j = 1; j < sqrtmaxa; j++) { v[j] += a[i] / j; } } ret *= -1; rep(i, 0, n) ret += (n - 1 - i) * a[i]; return ret; } S error_sq() { // (A - B)^2 // O(N) S ret = 0; rep(i, 0, n) ret += (S)a[i] * a[i]; ret *= (n - 1); ret += mul() * (-2); return ret; } S max() { // max(A, B) // O(N) S ret = 0; vector b = a; sort(b.begin(), b.end()); rep(i, 0, n) ret += (S)i * b[i]; return ret; } S min() { // min(A, B) // O(N) S ret = 0; vector b = a; sort(b.rbegin(), b.rend()); rep(i, 0, n) ret += (S)i * b[i]; return ret; } S error() { // |A - B| // O(N) S ret = 0; vector b = a; sort(b.rbegin(), b.rend()); rep(i, 0, n) ret += (S)(n - 1 - i * 2) * b[i]; return ret; } S xor_() { // A xor B // O(N log maxA) T mx = *max_element(a.begin(), a.end()); S ret = 0; int base = 0; while (mx >> base) { vector cnt(2); rep(i, 0, n) cnt[(a[i] >> base) & 1]++; ret += (S)(1LL << base) * (cnt[0] * cnt[1]); base++; } return ret; } S and_() { // A & B // O(N log maxA) T mx = *max_element(a.begin(), a.end()); S ret = 0; int base = 0; while (mx >> base) { vector cnt(2); rep(i, 0, n) cnt[(a[i] >> base) & 1]++; ret += (S)(1LL << base) * (cnt[1] * (cnt[1] - 1) / 2); base++; } return ret; } S or_() { // A | B // O(N log maxA) T mx = *max_element(a.begin(), a.end()); S ret = 0; int base = 0; while (mx >> base) { vector cnt(2); rep(i, 0, n) cnt[(a[i] >> base) & 1]++; ret += (S)(1LL << base) * (n * (n - 1) / 2 - cnt[0] * (cnt[0] - 1) / 2); base++; } return ret; } S lcm() { // lcm(A, B) // O(maxA log maxA) T m = *max_element(a.begin(), a.end()); vector w(m + 1); rep(i, 1, m + 1) { w[i] += (S)1 / i; int di = i + i; while (di <= m) { w[di] -= w[i]; di += i; } } vector b(m + 1); rep(i, 0, n) b[a[i]]++; S ret = 0; rep(i, 1, m + 1) { ll di = i; S sm = 0; while (di <= m) { sm += (S)b[di] * di; di += i; } ret += (S)w[i] * sm * sm; } rep(i, 0, n) ret -= a[i]; ret /= 2; return ret; } S gcd() { // gcd(A, B) // O(maxA log maxA) T m = *max_element(a.begin(), a.end()); vector w(m + 1); rep(i, 1, m + 1) { w[i] += i; int di = i + i; while (di <= m) { w[di] -= w[i]; di += i; } } vector b(m + 1); rep(i, 0, n) b[a[i]]++; S ret = 0; rep(i, 1, m + 1) { ll di = i; S sm = 0; while (di <= m) { sm += b[di]; di += i; } ret += (S)w[i] * sm * sm; } rep(i, 0, n) ret -= a[i]; ret /= 2; return ret; } }; int main() { ll n; cin >> n; vector a(n); rep(i, 0, n) a[i] = i + 1; reverse(a.begin(), a.end()); AllPairOperationSum op(a); ll ans = op.floor() + n; cout << ans << endl; }