QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#254201#7792. Tree Topological Order Countinghos_lyric100 ✓214ms102008kbC++146.0kb2023-11-18 04:35:342023-11-18 04:35:35

Judging History

你现在查看的是最新测评结果

  • [2023-11-18 04:35:35]
  • 评测
  • 测评结果:100
  • 用时:214ms
  • 内存:102008kb
  • [2023-11-18 04:35:34]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0U) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

constexpr unsigned MO = 1000000007;
using Mint = ModInt<MO>;

constexpr int LIM_INV = 5010;
Mint inv[LIM_INV], fac[LIM_INV], invFac[LIM_INV];

void prepare() {
  inv[1] = 1;
  for (int i = 2; i < LIM_INV; ++i) {
    inv[i] = -((Mint::M / i) * inv[Mint::M % i]);
  }
  fac[0] = invFac[0] = 1;
  for (int i = 1; i < LIM_INV; ++i) {
    fac[i] = fac[i - 1] * i;
    invFac[i] = invFac[i - 1] * inv[i];
  }
}
Mint binom(Int n, Int k) {
  if (n < 0) {
    if (k >= 0) {
      return ((k & 1) ? -1 : +1) * binom(-n + k - 1, k);
    } else if (n - k >= 0) {
      return (((n - k) & 1) ? -1 : +1) * binom(-k - 1, n - k);
    } else {
      return 0;
    }
  } else {
    if (0 <= k && k <= n) {
      assert(n < LIM_INV);
      return fac[n] * invFac[k] * invFac[n - k];
    } else {
      return 0;
    }
  }
}


int N;
vector<int> P;
vector<Mint> B;

/*
  random topological sort = random coloring, probability proportional to sz[u]
  dp[u][k] := N^(fall k) Pr[after k rounds, par[u] is colored and u is not colored]
*/
Mint dp[5010][5010];

int main() {
  prepare();
  
  for (; ~scanf("%d", &N); ) {
    P.resize(N);
    for (int u = 1; u < N; ++u) {
      scanf("%d", &P[u]);
      --P[u];
    }
    P[0] = -1;
    B.resize(N);
    for (int k = 0; k < N; ++k) {
      scanf("%u", &B[k].x);
    }
    
    vector<int> sz(N, 1);
    for (int u = N; --u >= 1; ) {
      sz[P[u]] += sz[u];
    }
    
    dp[0][0] = 1;
    for (int u = 1; u < N; ++u) {
      for (int k = 0; k < N; ++k) {
        dp[u][k + 1] = (N - k - sz[u]) * dp[u][k] + sz[P[u]] * dp[P[u]][k];
      }
// cerr<<"dp["<<u<<"] = ";pv(dp[u],dp[u]+(N+1));
    }
    
    // dp[u][k] <- N! Pr[u is colored exactly in the k-th round]
    for (int u = 0; u < N; ++u) {
      for (int k = 0; k < N; ++k) {
        dp[u][k] *= sz[u] * fac[N - k - 1];
      }
// cerr<<"dp["<<u<<"] = ";pv(dp[u],dp[u]+(N+1));
    }
    
    Mint prodInvSz = 1;
    for (int u = 0; u < N; ++u) {
      prodInvSz *= inv[sz[u]];
    }
    vector<Mint> ans(N, 0);
    for (int u = 0; u < N; ++u) {
      for (int k = 0; k < N; ++k) {
        ans[u] += dp[u][k] * B[k];
      }
      ans[u] *= prodInvSz;
    }
    
    for (int u = 0; u < N; ++u) {
      if (u) printf(" ");
      printf("%u", ans[u].x);
    }
    puts("");
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 1ms
memory: 3956kb

input:

10
1 2 2 4 2 5 3 2 3
421487749 899442061 973943239 478653728 122912827 681073947 761973567 862016787 295035337 313094543

output:

132551152 750202542 844925059 844925059 320019016 837104208 346368542 333193779 837104208 333193779

result:

ok 10 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 4168kb

input:

10
1 2 2 4 5 4 3 7 1
226457597 222460848 126601784 27445914 811511381 52803670 776934531 832659037 955599897 927944188

output:

802913206 192357888 80729172 288305444 609011662 689888737 609011662 673713322 689888737 479113328

result:

ok 10 numbers

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #3:

score: 10
Accepted
time: 0ms
memory: 3996kb

input:

20
1 1 1 4 2 5 2 5 4 6 4 7 11 11 2 9 7 2 9
305559508 68914843 154933697 736516347 250860247 264123902 632865608 32202124 861284820 505164728 564475479 136404892 645017283 837805203 802302363 50345521 511083407 292719502 356887812 390453540

output:

4420887 270322976 277088290 558845717 651457501 42292358 346897100 706626195 346897100 468004133 556186525 468004133 982694311 614012945 614012945 706626195 982694311 982694311 706626195 982694311

result:

ok 20 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 3864kb

input:

20
1 1 2 1 3 4 4 4 6 10 2 12 4 8 14 9 7 16 15
691946539 440256927 968885281 472566141 20270022 183480725 684128023 668848432 366950038 421741447 88719369 679972163 897823307 376002875 147228549 89583310 930341312 627165235 998616162 46722211

output:

245904036 40491473 208122274 756122338 801039801 614916526 509450260 868456290 509450260 693529082 687591315 99754271 773178914 868456290 791438207 791438207 599551778 599551778 3608560 3608560

result:

ok 20 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

20
1 1 1 1 1 1 1 1 1 1 1 10 10 6 15 9 17 7 4
288280511 16879884 428044913 511311984 847245966 72822732 803411803 664704151 974477820 303440613 592210469 341084543 683099992 713223966 417890386 967156434 18771827 81816553 193725635 158295200

output:

207513772 350702711 350702711 146536641 350702711 195759251 146536641 350702711 195759251 195759251 350702711 350702711 428174441 428174441 48091421 808257461 48091421 808257461 554868781 554868781

result:

ok 20 numbers

Subtask #3:

score: 15
Accepted

Dependency #2:

100%
Accepted

Test #6:

score: 15
Accepted
time: 1ms
memory: 4264kb

input:

100
1 1 1 1 5 2 2 8 8 2 11 1 8 6 8 15 15 8 11 7 14 12 10 12 15 4 12 2 11 2 1 12 6 9 12 36 1 20 15 22 20 11 28 35 8 6 47 26 1 50 26 52 20 51 5 16 7 22 30 25 9 40 4 11 9 35 49 32 3 68 35 50 70 52 2 26 14 15 26 37 72 23 30 41 9 31 32 73 16 13 40 39 32 36 83 23 42 48 8
499370580 226348607 730860505 6961...

output:

378504482 152270968 588856846 588856846 451796857 507053458 485397893 343836957 802668753 637426492 386300892 166332977 516615074 434547603 230818994 362763740 197266323 197266323 619220872 369540656 981420869 809135769 398229189 601015252 83277609 749643676 903903231 83277609 816079877 802671417 29...

result:

ok 100 numbers

Test #7:

score: 0
Accepted
time: 1ms
memory: 4260kb

input:

100
1 2 3 4 3 3 7 8 9 10 10 12 12 10 7 16 16 18 19 20 21 21 20 24 24 26 27 19 29 30 31 18 33 34 35 36 34 38 39 40 41 42 43 42 42 41 39 48 49 48 48 52 53 38 55 18 57 58 59 60 58 62 63 64 65 66 65 68 69 70 70 65 73 74 64 76 77 78 78 80 78 78 83 84 76 86 62 88 89 90 89 57 93 94 95 95 97 7 3 577441326 8...

output:

24745333 332372584 221230837 905244609 871647923 888446266 767512902 623574378 656235660 415629913 849746614 719923753 414658041 414658041 849746614 402205168 526141339 849958506 971879651 443767080 822469942 831691587 831691587 58824397 437732695 467938249 631371835 213888001 566609539 751780666 27...

result:

ok 100 numbers

Test #8:

score: 0
Accepted
time: 1ms
memory: 4548kb

input:

100
1 1 1 2 5 1 5 6 6 3 6 5 13 14 15 16 6 17 19 1 3 20 3 19 23 1 21 28 26 22 30 27 32 29 31 34 10 11 12 37 36 41 43 21 44 46 29 47 49 22 50 52 53 42 16 54 57 35 27 58 61 17 22 30 62 59 66 19 14 55 56 68 67 74 75 76 73 78 77 79 80 42 82 81 85 86 87 71 88 84 91 12 92 89 94 90 37 54 89
605221076 121774...

output:

191199508 4617006 808901507 566404623 124140965 162213750 566404623 864721314 393650962 90732392 258608983 518925993 633131612 162920052 325151707 741164232 456177120 393650962 156411701 632463088 874398001 118929519 953485256 16904827 758670923 629168678 312375353 29155254 13159381 848358851 402682...

result:

ok 100 numbers

Test #9:

score: 0
Accepted
time: 1ms
memory: 4548kb

input:

100
1 1 2 4 5 3 7 6 6 10 6 11 13 6 14 9 16 8 18 20 21 20 19 14 22 26 24 7 8 28 27 32 31 28 34 36 33 38 39 40 41 37 42 44 45 46 47 48 43 13 49 52 53 50 45 54 57 55 59 58 61 31 30 50 60 62 18 68 67 70 22 7 73 74 20 71 77 78 79 80 5 81 66 83 85 16 35 71 86 33 90 84 92 94 95 75 93 51 99
167324337 235996...

output:

960069110 565410671 378415579 83061265 251033682 837557317 949670974 227661063 135094654 196352221 204104597 467559995 962078051 500880733 467559995 820376189 800025336 137849548 861007463 253383929 672706993 444274725 686270519 26681153 853944822 838947777 356454261 823074879 449754211 242297513 79...

result:

ok 100 numbers

Test #10:

score: 0
Accepted
time: 1ms
memory: 4288kb

input:

100
1 2 2 3 3 4 4 5 1 10 10 11 11 12 12 13 1 18 18 19 19 20 20 21 1 26 26 27 27 28 28 29 1 34 34 35 35 36 36 37 1 42 42 43 43 44 44 45 1 50 50 51 51 52 52 53 1 58 58 59 59 60 60 61 35 37 53 33 38 12 47 4 12 31 39 43 71 28 3 44 26 4 56 10 36 23 48 75 23 33 64 37 61 58 72 6 19 80 76
624084541 43803720...

output:

945263113 879084197 191295526 536463760 604811148 604811148 247555643 247555643 910543971 917658385 625486473 820518005 529128244 491159688 165586058 165586058 453191132 65531338 567934672 567934672 188036476 316886889 299902261 316886889 445737302 586518136 331015734 331015734 70230621 250098181 40...

result:

ok 100 numbers

Test #11:

score: 0
Accepted
time: 1ms
memory: 4516kb

input:

100
1 2 3 4 5 6 7 8 8 9 9 10 10 1 15 16 17 18 19 20 21 21 22 22 23 23 1 28 29 30 31 32 33 34 34 35 35 36 36 1 41 42 43 44 45 46 47 47 48 48 49 49 1 54 55 56 57 58 59 60 60 61 61 62 62 1 67 68 69 70 71 72 73 73 74 74 75 75 1 80 81 82 83 84 85 86 86 87 87 88 88 69 92 58 43 66 60 77 52
390699613 651233...

output:

65621655 812092562 932235668 4003220 261644586 935856346 722411218 785121698 535820036 535820036 416920411 416920411 416920411 416920411 812092562 932235668 4003220 261644586 935856346 722411218 785121698 535820036 535820036 416920411 416920411 416920411 416920411 812092562 932235668 4003220 2616445...

result:

ok 100 numbers

Test #12:

score: 0
Accepted
time: 1ms
memory: 4544kb

input:

100
1 2 3 3 3 3 2 2 9 1 4 4 2 7 13 5 5 8 17 16 12 16 10 6 11 24 16 23 25 12 24 16 22 26 34 30 19 23 24 38 25 31 30 28 1 37 41 45 43 15 47 37 42 39 27 53 28 13 43 53 27 53 32 62 60 2 26 14 14 14 58 22 7 5 69 34 28 54 32 14 1 77 37 31 19 35 28 25 15 59 20 39 73 60 70 15 88 75 23
746243501 189811510 61...

output:

598979168 872241254 50503028 74493216 383279680 569030711 148205445 957505231 371091216 128352247 791181979 82141350 404645980 135863973 283785015 732518603 793451753 976035964 897131493 436880141 157275854 157217864 445433968 636821036 727813431 691029440 742701790 572299015 499644234 203584758 157...

result:

ok 100 numbers

Test #13:

score: 0
Accepted
time: 1ms
memory: 4268kb

input:

100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 52 39 57 88 20 18 42 96 23 95
203758586 574528415 435665491 34474532 638409977 850247931 218570973 588307431 581460307...

output:

669437192 513943159 513943159 513943159 513943159 513943159 513943159 513943159 513943159 513943159 513943159 513943159 513943159 513943159 513943159 513943159 513943159 193584960 513943159 193584960 513943159 513943159 496316739 513943159 513943159 513943159 513943159 513943159 513943159 513943159 ...

result:

ok 100 numbers

Subtask #4:

score: 15
Accepted

Dependency #3:

100%
Accepted

Test #14:

score: 15
Accepted
time: 2ms
memory: 5704kb

input:

350
1 2 2 3 4 1 4 5 4 3 10 4 9 2 1 14 17 5 18 14 12 18 12 21 22 3 9 12 20 19 14 13 29 18 16 16 4 7 3 4 38 4 3 43 36 37 44 1 6 14 40 49 38 46 28 55 42 48 54 21 60 5 35 36 7 1 13 56 9 56 34 6 50 25 37 26 28 26 16 69 54 2 80 18 26 24 47 1 28 15 54 64 69 77 27 90 39 11 58 25 34 48 18 71 63 10 48 64 12 8...

output:

725457781 985623070 549707882 708594727 328876909 317926772 563675054 233391385 624039021 803646801 298937586 524128692 318027847 920041380 86020600 999877879 723757052 769897066 948867117 147083007 167157273 132987474 224599204 684173661 510745536 932881263 631107585 992223949 941708044 40102442 13...

result:

ok 350 numbers

Test #15:

score: 0
Accepted
time: 0ms
memory: 5728kb

input:

350
1 2 3 4 4 6 7 8 8 10 8 12 13 14 15 14 17 17 19 20 20 19 19 8 25 26 27 28 28 30 31 28 33 27 35 3 37 38 39 40 41 41 43 44 45 46 47 48 49 50 51 50 53 54 55 56 57 56 59 60 61 62 63 64 59 66 55 68 69 70 70 68 73 74 75 76 77 78 79 80 79 82 83 84 84 86 87 88 89 88 91 92 92 87 95 95 97 95 99 100 101 100...

output:

188958962 838018032 694894789 823120892 617644783 530274027 200969947 240826756 613389912 179693701 47086116 672985728 107813167 154260189 293594073 914207880 621041278 601452362 721957774 10662830 660695503 660695503 777351281 777351281 860280148 499574250 911926383 445146999 511406743 805488190 81...

result:

ok 350 numbers

Test #16:

score: 0
Accepted
time: 2ms
memory: 5800kb

input:

350
1 1 1 2 1 5 1 4 8 10 11 12 5 7 13 7 15 5 18 16 20 20 21 24 25 13 22 5 3 26 6 30 32 28 2 17 35 38 39 34 15 33 34 31 8 45 47 6 33 48 20 38 44 14 40 51 57 58 21 59 61 62 63 3 56 56 24 11 67 64 43 71 42 73 75 60 60 70 57 76 81 79 12 82 29 35 85 83 88 58 88 92 93 94 89 95 97 98 48 99 96 65 54 3 104 1...

output:

438897019 541316843 201876893 85374434 9104378 420007743 966687576 870883857 675222175 214716492 250600570 57960264 632987803 612496263 3227598 750983699 900689888 944006702 298215074 512176985 862670964 171318357 774442976 288733555 854690910 645160240 87885048 589713021 902647307 703952580 5232017...

result:

ok 350 numbers

Test #17:

score: 0
Accepted
time: 2ms
memory: 5732kb

input:

350
1 1 3 4 5 1 2 2 9 10 11 4 3 6 15 15 13 17 19 7 20 1 22 24 25 21 27 25 28 9 26 32 30 33 35 34 36 37 38 19 41 42 43 44 45 46 47 48 49 49 51 51 53 45 55 43 57 43 59 60 61 62 63 63 65 65 67 65 62 70 71 61 73 74 73 76 76 61 79 80 40 82 83 84 85 20 86 88 89 22 77 87 90 94 95 96 97 98 39 100 99 102 103...

output:

898527269 482984035 686126059 557584585 675389346 420572461 672969385 110990278 400363869 875184105 362664271 839931847 964530344 273367959 210515998 660292792 368931832 633266578 641794985 465418933 977524707 536041134 818989589 337536438 119143856 956853355 436911204 170099986 324969275 20107466 5...

result:

ok 350 numbers

Test #18:

score: 0
Accepted
time: 0ms
memory: 7152kb

input:

350
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 1 17 17 18 18 19 19 20 20 21 21 22 22 23 23 1 32 32 33 33 34 34 35 35 36 36 37 37 38 38 1 47 47 48 48 49 49 50 50 51 51 52 52 53 53 1 62 62 63 63 64 64 65 65 66 66 67 67 68 68 1 77 77 78 78 79 79 80 80 81 81 82 82 83 83 1 92 92 93 93 94 94 95 95 96 96 97 97 98 98 1 ...

output:

48923942 23270472 101399992 863794196 357111863 357111863 629259141 359151893 241404561 478445221 530122833 478445221 804943283 443382868 824838671 757685379 382912364 429284275 429284275 55165442 356075503 52631158 356075503 666305018 421620803 445742475 866780580 580229256 580229256 681536014 8667...

result:

ok 350 numbers

Test #19:

score: 0
Accepted
time: 2ms
memory: 7472kb

input:

350
1 2 3 4 5 6 7 8 9 10 11 12 13 14 14 15 15 16 16 17 17 18 18 19 19 1 27 28 29 30 31 32 33 34 35 36 37 38 39 39 40 40 41 41 42 42 43 43 44 44 1 52 53 54 55 56 57 58 59 60 61 62 63 64 64 65 65 66 66 67 67 68 68 69 69 1 77 78 79 80 81 82 83 84 85 86 87 88 89 89 90 90 91 91 92 92 93 93 94 94 1 102 10...

output:

883509303 979582152 230506070 603418923 629288117 91202416 175046645 406546458 234248100 820358756 149965837 874704455 908347504 75898074 68078909 648992377 569849990 569849990 913524544 975036339 390253478 390253478 390253478 390253478 505792233 505792233 979582152 230506070 603418923 629288117 912...

result:

ok 350 numbers

Test #20:

score: 0
Accepted
time: 0ms
memory: 5732kb

input:

350
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64...

output:

628936700 683760690 193765126 909619921 346017938 876319429 673543524 496433333 749368867 357631037 164329002 253087228 78140650 210017699 315466616 602875574 537134073 821763142 210696656 878230841 786231942 997041178 516917338 841390659 975607427 885621439 62184466 85620355 135353876 533113271 843...

result:

ok 350 numbers

Test #21:

score: 0
Accepted
time: 0ms
memory: 5712kb

input:

350
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

556123465 527303785 527303785 527303785 363819617 144927891 527303785 767804502 527303785 527303785 363819617 527303785 363819617 767804502 527303785 527303785 527303785 767804502 527303785 527303785 527303785 527303785 363819617 767804502 527303785 527303785 144927891 767804502 363819617 929215879 ...

result:

ok 350 numbers

Subtask #5:

score: 15
Accepted

Test #22:

score: 15
Accepted
time: 73ms
memory: 58712kb

input:

3000
1 1 3 1 3 6 1 5 3 2 4 9 6 7 2 7 1 1 8 1 4 17 23 2 5 24 15 12 14 28 16 32 33 16 6 1 3 12 17 31 33 19 43 3 33 7 35 42 23 15 30 12 8 21 16 38 53 8 49 56 21 25 30 54 30 14 20 10 35 28 35 55 12 50 10 1 75 76 19 22 8 82 4 68 42 9 57 68 3 67 56 8 11 23 72 68 9 62 32 20 73 39 74 56 88 61 83 78 69 29 29...

output:

16671810 944499931 273506025 607998113 446862295 158970004 442911964 756220225 307986370 536953966 336880452 789379781 300103944 158249160 867664998 83631453 17442425 491509604 588320809 724419565 130536659 790581701 659232050 490335021 392240369 593172088 328309069 347269844 39252086 682905115 5195...

result:

ok 3000 numbers

Test #23:

score: 0
Accepted
time: 86ms
memory: 59488kb

input:

3000
1 1 3 4 4 5 7 8 8 10 3 11 13 14 15 11 16 18 2 3 18 22 4 23 25 26 27 28 29 30 31 32 8 33 35 29 36 38 39 40 18 41 43 44 45 46 47 7 48 50 51 52 9 53 55 16 56 12 58 60 6 49 61 64 65 66 67 68 69 70 71 72 73 74 75 62 76 78 79 80 81 4 82 84 85 86 54 87 89 90 91 92 38 93 95 58 96 98 72 99 101 91 95 102...

output:

44908844 990215062 623923044 718955659 504471765 600516189 289987871 773488868 973079077 535553649 430565772 453426415 809315225 188064671 566814124 128726905 601002839 684802533 47014986 935521273 697681475 56980478 429158430 736450408 953652904 478147371 2641838 527136312 51630779 520957673 990284...

result:

ok 3000 numbers

Test #24:

score: 0
Accepted
time: 78ms
memory: 59896kb

input:

3000
1 2 3 4 5 4 7 8 7 10 10 12 7 14 14 16 16 16 16 20 20 22 23 22 4 26 26 28 29 30 31 30 33 33 29 36 37 38 39 40 41 39 43 44 45 46 47 48 49 50 51 52 53 53 55 55 57 58 59 60 61 61 63 64 65 63 57 68 52 51 51 49 49 46 75 76 77 77 79 80 79 77 75 84 84 84 87 45 45 90 44 43 37 37 36 28 97 97 99 100 101 1...

output:

247480365 494960730 742441095 469543270 542552237 615561204 330494614 449853133 569211652 202109724 945339951 697596542 193083353 588808120 138689142 870604672 279587418 279587418 279587418 130314024 909442101 41965252 257500225 473035198 865267715 812596936 250583550 36243007 828305725 808343503 76...

result:

ok 3000 numbers

Test #25:

score: 0
Accepted
time: 77ms
memory: 59620kb

input:

3000
1 1 1 1 4 6 7 5 9 3 8 12 12 13 3 10 3 10 17 19 15 20 23 22 25 24 13 2 16 26 17 24 33 34 31 21 36 38 39 35 40 42 43 44 41 45 47 48 49 46 50 52 53 42 51 54 28 56 59 36 57 62 30 30 60 42 17 63 45 69 71 63 13 32 72 76 77 42 78 7 80 82 83 83 84 66 87 1 6 86 67 82 28 46 91 96 97 88 98 92 99 100 102 1...

output:

226967776 710854985 721596848 176918949 537111677 269965673 970351043 381083215 112155114 687198558 925943932 791815394 618121193 659510517 244486892 362466262 949843979 925943932 992585117 984900848 182202761 554951282 164906382 120403160 865415672 175880055 625347088 769338176 194742187 116031210 ...

result:

ok 3000 numbers

Test #26:

score: 0
Accepted
time: 57ms
memory: 58312kb

input:

3000
1 1 2 4 5 3 7 7 6 10 9 12 11 1 13 15 16 17 14 3 21 22 23 24 24 26 27 28 29 29 31 31 33 28 35 27 27 38 39 40 41 27 43 27 26 46 46 48 23 50 51 51 53 54 55 56 56 58 56 60 61 60 54 64 65 66 67 68 69 66 66 65 73 64 64 76 77 78 79 80 81 76 83 83 85 86 85 88 64 90 64 64 54 94 95 50 97 98 97 100 101 10...

output:

549180254 443840833 25507275 338501412 20110357 701719309 570159443 474113698 87402998 429473072 157226835 604646560 121890115 884980605 575182842 639133677 890565241 804891944 990247983 863138903 651752105 767289759 882827413 183036329 485334461 954226476 679654644 130510980 375438449 732684587 494...

result:

ok 3000 numbers

Test #27:

score: 0
Accepted
time: 89ms
memory: 57484kb

input:

3000
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 1 47 47 48 48 49 49 50 50 51 51 52 52 53 53 54 54 55 55 56 56 57 57 58 58 59 59 60 60 61 61 62 62 63 63 64 64 65 65 66 66 67 67 68 68 1 92 92 93 93 94 94 95 95 96 96 97 97 98 98...

output:

213776412 734545658 263622594 777096304 627591863 449682827 210360993 372835254 438084231 284860312 59015334 957459922 293522726 599135484 165378420 165378420 964315158 595930474 599397217 536489836 930013487 973014105 16014716 250233920 918265329 918265329 835103596 71071701 854193176 854193176 854...

result:

ok 3000 numbers

Test #28:

score: 0
Accepted
time: 81ms
memory: 58676kb

input:

3000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 53 54 54 55 55 56 56 57 1 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

output:

112467926 130237238 148006550 165775862 183545174 201314486 219083798 236853110 254622422 272391734 290161046 307930358 325699670 343468982 361238294 379007606 396776918 414546230 432315542 450084854 467854166 485623478 503392790 664336555 825280320 986224085 147167843 308111608 469055373 629999138 ...

result:

ok 3000 numbers

Test #29:

score: 0
Accepted
time: 86ms
memory: 57508kb

input:

3000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

output:

336741315 555628554 774515793 321689801 868863816 675244769 478550933 281857097 127795039 973732988 224936656 375637747 526338838 485637068 992737827 499838579 6939331 648342626 289745914 410095147 530444380 951418004 410552169 869686341 328820506 787954678 247088843 706223015 689143470 672063925 65...

result:

ok 3000 numbers

Test #30:

score: 0
Accepted
time: 81ms
memory: 57976kb

input:

3000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

993026631 19650673 19650673 532962701 532962701 19650673 532962701 532962701 532962701 718722650 532962701 506338652 532962701 19650673 532962701 532962701 532962701 532962701 532962701 762994666 532962701 762994666 809001059 532962701 532962701 532962701 532962701 532962701 809001059 19650673 19650...

result:

ok 3000 numbers

Test #31:

score: 0
Accepted
time: 73ms
memory: 59212kb

input:

3000
1 1 2 4 4 6 7 8 9 10 11 12 13 14 15 7 17 16 14 19 5 21 23 9 24 7 26 21 28 3 30 32 25 33 24 35 37 38 26 39 25 7 41 44 45 46 47 25 48 50 22 2 51 54 26 55 57 58 59 60 57 61 57 63 65 11 66 27 62 68 71 5 13 72 75 76 77 78 79 80 81 29 24 82 82 86 87 88 4 89 91 92 21 93 66 95 97 73 98 100 30 101 103 1...

output:

401216826 653273841 766263786 36472228 895788544 695944124 890996741 418668947 946341160 251837860 807097375 205402054 233098623 573118731 855795024 548914929 523134671 787410538 449297039 893016424 349679149 614421162 892621644 678216845 658420290 648575328 277893291 102336080 619879876 284456106 5...

result:

ok 3000 numbers

Subtask #6:

score: 20
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #32:

score: 20
Accepted
time: 82ms
memory: 57792kb

input:

3000
1 2 1 4 2 6 1 7 1 5 5 4 4 12 5 12 15 2 7 13 10 8 8 9 25 6 5 14 5 2 19 31 32 29 35 13 35 37 19 26 41 27 15 18 38 34 47 32 18 2 50 5 20 4 3 36 9 44 20 58 47 42 41 13 51 20 56 25 44 5 49 54 23 21 52 18 10 78 36 69 1 33 12 21 28 59 60 35 44 61 36 63 60 59 15 76 50 88 44 17 76 97 82 1 84 42 86 29 12...

output:

852540635 95304126 197674837 26264999 329078163 314315809 976592046 915329774 547882644 769845186 945404475 756206471 254644551 410589380 296973786 230648501 878818991 669980615 462800229 664845564 414743185 884566196 399949374 262880917 220170476 577567952 550004153 417174395 557307110 60361570 887...

result:

ok 3000 numbers

Test #33:

score: 0
Accepted
time: 67ms
memory: 58016kb

input:

3000
1 2 1 4 5 3 6 4 8 3 10 12 13 14 15 16 4 9 17 1 20 22 23 17 24 26 27 16 9 28 31 32 33 34 7 35 37 27 38 40 2 41 43 44 45 46 47 48 49 50 51 52 9 53 55 56 33 57 59 17 60 19 27 62 65 66 8 17 67 70 71 11 39 72 75 76 43 77 79 80 81 46 82 84 85 86 87 64 47 88 91 92 93 94 89 95 97 98 45 100 101 102 103 ...

output:

873295693 23639289 721161624 94492431 653318397 528654114 423322488 146106719 34871361 120758144 13298453 658056719 200020118 404075067 317575401 991637529 973822630 792690900 740931714 947147429 841654020 434768521 83428880 534227948 837445967 206187122 909690683 699183942 732478732 544254805 51822...

result:

ok 3000 numbers

Test #34:

score: 0
Accepted
time: 80ms
memory: 59268kb

input:

3000
1 2 3 4 5 6 7 8 9 10 4 12 13 14 15 16 17 14 19 19 21 19 2 24 25 26 27 28 29 30 31 31 33 34 35 36 37 37 39 30 41 42 43 28 45 45 47 47 49 50 51 49 53 54 53 56 53 58 49 60 49 62 63 64 64 66 67 68 69 68 71 72 73 71 75 76 77 78 79 80 79 82 83 84 84 84 87 88 89 87 91 92 93 94 95 96 97 96 92 100 101 1...

output:

77518560 304555639 640667582 358495774 376069411 773007034 237927377 814364446 846791929 914976390 2640056 213639752 35880814 915582268 727301073 427730743 155547745 367744235 123152821 493687981 138151573 849224389 493687981 834044139 165976106 21291248 225204593 529395278 440995580 115632744 44206...

result:

ok 3000 numbers

Test #35:

score: 0
Accepted
time: 62ms
memory: 57868kb

input:

3000
1 1 2 1 3 5 3 7 3 8 9 12 13 10 14 16 4 17 6 19 21 22 23 24 12 15 25 28 3 29 31 32 27 33 35 36 37 34 39 38 35 41 21 40 33 8 43 45 49 48 51 52 53 54 55 38 10 31 56 36 15 60 63 64 65 50 48 9 66 22 67 24 70 74 75 76 77 78 72 79 38 80 81 67 84 83 82 86 89 87 90 1 91 92 54 95 56 35 97 66 100 65 102 9...

output:

377068019 380329075 591480714 578613459 51720914 484803379 96104417 498777287 307005216 522785867 730274852 36836365 693609757 702306106 401298385 963966157 581368419 842038249 614972307 660928584 495045316 440374230 616359477 738487168 265975527 501645119 848739207 436336728 103659407 72865978 7440...

result:

ok 3000 numbers

Test #36:

score: 0
Accepted
time: 89ms
memory: 58268kb

input:

3000
1 1 2 4 3 5 5 7 3 9 11 10 13 14 12 16 17 18 19 20 1 21 5 19 23 22 15 26 29 15 30 11 29 32 28 11 35 38 27 14 39 42 36 23 25 44 22 48 49 50 51 52 53 54 55 56 53 58 58 60 61 62 63 61 60 66 67 68 69 70 69 72 67 74 75 76 77 78 79 78 81 82 66 84 85 86 87 88 89 90 91 85 84 94 84 96 60 98 99 98 101 102...

output:

446849274 597622408 232202260 353194306 462577521 178964987 772583263 49069207 64290754 299670247 24996010 821646059 638986326 524053489 677965606 915818795 150643406 393392694 284625564 375770322 570361081 209241146 386280615 49069207 643501680 690510679 31800067 514134531 632747964 923391900 97039...

result:

ok 3000 numbers

Test #37:

score: 0
Accepted
time: 75ms
memory: 57912kb

input:

3000
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 1 47 47 48 48 49 49 50 50 51 51 52 52 53 53 54 54 55 55 56 56 57 57 58 58 59 59 60 60 61 61 62 62 63 63 64 64 65 65 66 66 67 67 68 68 1 92 92 93 93 94 94 95 95 96 96 97 97 98 98...

output:

361729088 626887943 789757644 230955429 208142848 434386735 490113268 490113268 938525600 856863861 725493497 274330773 363470230 695231484 695231484 802160628 524365792 291891260 449885577 244488669 679524261 316035409 558865084 14394077 527700217 527700217 56603305 417388239 417388239 56603305 221...

result:

ok 3000 numbers

Test #38:

score: 0
Accepted
time: 66ms
memory: 59820kb

input:

3000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 53 54 54 55 55 56 56 57 1 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

output:

190349299 79729768 314617539 322670888 424228281 891501030 559058873 413438753 422128981 829816123 213677514 550030514 181567812 230441332 791102331 753483253 291903616 819222611 113188483 193407077 840420259 412954023 704421470 118503034 738504938 900752542 212440694 664018416 25187701 946186494 67...

result:

ok 3000 numbers

Test #39:

score: 0
Accepted
time: 82ms
memory: 57952kb

input:

3000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

output:

225130290 753073456 805007449 527041803 411202023 530504776 94551263 3041570 350855584 110122944 865291468 631031294 276963309 735249102 643532693 478499314 931307502 683316101 256183780 536909348 814432365 376511106 407434051 823377871 362068584 421137799 747174124 411163513 602788959 445143602 120...

result:

ok 3000 numbers

Test #40:

score: 0
Accepted
time: 81ms
memory: 59112kb

input:

3000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

998237435 206235565 138144624 206235565 138144624 138144624 206235565 206235565 138144624 43470929 206235565 229749647 206235565 206235565 206235565 138144624 206235565 138144624 138144624 138144624 206235565 138144624 206235565 206235565 206235565 206235565 206235565 206235565 138144624 43470929 20...

result:

ok 3000 numbers

Test #41:

score: 0
Accepted
time: 78ms
memory: 58080kb

input:

3000
1 1 2 4 3 2 7 8 9 10 11 1 7 3 12 10 12 18 19 20 21 22 23 5 24 26 27 28 29 29 30 32 33 30 34 8 26 19 36 34 40 42 35 43 37 2 45 48 36 49 32 51 53 54 55 56 57 58 59 60 61 62 63 64 65 23 66 68 69 70 71 72 73 74 75 5 50 76 79 80 81 38 82 84 85 86 29 60 87 84 90 92 93 94 95 11 96 98 99 100 78 101 103...

output:

6739718 999436990 158069224 124299219 772178839 964807240 200640982 107953582 560889935 693217449 597260034 80428683 912575906 84645187 119510347 22388697 144071238 727484027 158756001 308748679 816731500 795344725 197662957 109781856 501091538 945098692 869670091 815746015 51882570 854341631 142006...

result:

ok 3000 numbers

Subtask #7:

score: 20
Accepted

Dependency #6:

100%
Accepted

Test #42:

score: 20
Accepted
time: 206ms
memory: 101716kb

input:

5000
1 2 3 1 5 4 7 1 8 1 1 10 6 5 15 14 2 3 9 3 3 3 23 22 3 19 20 22 24 2 1 7 15 26 21 23 11 33 33 2 17 34 37 22 39 7 44 24 17 20 42 29 2 24 3 55 6 21 18 2 28 24 50 62 56 18 62 57 34 45 69 12 30 21 54 58 63 34 74 35 41 76 20 22 81 21 41 32 21 17 91 50 77 31 35 55 71 2 65 45 97 67 31 94 60 93 14 67 4...

output:

100856182 480065093 290494959 520628160 141876008 881740008 835692115 61491100 89306181 257223622 43069705 778973907 8769221 841216203 813513479 307859492 725658293 397798223 349068814 924545417 975426339 336613830 213823554 734188669 545139077 98357832 833048709 344007369 881604883 281722872 179449...

result:

ok 5000 numbers

Test #43:

score: 0
Accepted
time: 202ms
memory: 101784kb

input:

5000
1 2 2 3 5 6 7 7 8 10 11 12 9 13 15 16 17 18 19 20 21 9 18 22 5 25 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 8 42 44 45 46 47 48 49 50 31 23 51 54 55 56 4 57 59 60 54 61 63 64 65 66 67 68 69 68 70 72 73 29 74 76 77 78 79 80 81 82 18 76 83 86 87 88 89 76 90 92 93 94 75 48 95 98 99 18 42 100 10...

output:

16790201 743667984 300917633 694445361 22200145 695351498 987586746 719838053 160033317 68082825 51738185 898251752 558374495 194693420 616367515 765342063 605373981 610792054 719665526 356724232 421584746 68792201 194693420 279631825 399682685 112248379 240320187 950208203 424477692 17096957 870943...

result:

ok 5000 numbers

Test #44:

score: 0
Accepted
time: 199ms
memory: 101848kb

input:

5000
1 2 3 4 5 6 5 8 8 10 11 4 13 3 15 16 17 17 19 20 3 22 3 24 25 24 27 28 29 30 29 2 33 33 35 36 37 38 39 40 40 38 43 44 45 46 47 45 45 50 51 43 36 54 54 56 57 57 59 57 61 62 63 64 65 63 63 68 69 68 68 72 73 73 75 76 72 78 79 80 81 81 83 84 85 86 86 78 89 89 91 72 68 56 95 96 96 98 98 100 101 102 ...

output:

573177129 661410021 792968579 821930658 722157676 639481276 69385756 51766440 430100285 888662600 316548293 85089962 660150376 140647696 470106475 955567723 135891557 218277813 752778922 891125245 10929279 235019515 460602487 299748696 502239751 455397829 590305422 992353779 812211268 392006752 2600...

result:

ok 5000 numbers

Test #45:

score: 0
Accepted
time: 205ms
memory: 101752kb

input:

5000
1 1 3 4 2 5 7 1 8 10 1 7 12 11 8 14 15 5 10 18 21 14 9 22 25 26 27 28 29 29 31 20 15 32 23 11 13 36 39 28 37 29 40 21 45 44 36 35 47 50 51 52 49 53 53 56 57 58 54 23 60 59 63 64 62 65 67 68 26 6 69 16 62 72 74 75 77 78 76 79 67 21 3 80 85 86 81 67 34 87 91 12 92 21 88 94 75 96 99 100 101 102 10...

output:

829130819 618531170 537075547 660882672 604449341 410321264 283236418 226808923 128854592 939788067 964038807 550274612 526979886 241032497 8277829 51655307 334675760 34029567 464482050 453970406 696774570 475566524 523641385 908733630 950793077 82133554 327712937 691701872 72922996 938167666 868276...

result:

ok 5000 numbers

Test #46:

score: 0
Accepted
time: 196ms
memory: 101784kb

input:

5000
1 2 3 4 1 1 6 5 4 7 4 10 13 8 11 2 16 14 19 18 3 20 21 23 8 11 25 28 29 30 18 31 18 33 35 7 36 24 15 38 39 41 40 44 32 38 43 48 49 42 51 24 52 50 32 55 54 45 21 58 59 57 63 19 41 61 56 64 41 23 52 69 67 73 42 74 75 78 79 28 80 82 77 83 78 85 62 84 88 87 90 91 26 91 93 89 97 24 77 92 101 96 103 ...

output:

412116096 204095895 525835821 758316248 167367518 996424906 461900230 146324055 648487137 134704098 67773162 907927331 282545086 278160753 298494601 518505831 40322672 133446982 372784376 677634627 347531632 719930251 417740962 791862341 913945210 750663095 831673296 906715117 675140955 931132832 93...

result:

ok 5000 numbers

Test #47:

score: 0
Accepted
time: 214ms
memory: 101776kb

input:

5000
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 1 61 61 62 62 63 63 64 64 65 65 66 66 67 67 68 68 69 69 70 70 71 71 72 72 73 73 74 74 75 75 76 76 77 77 78 78 79 79 80 80 81 81 82 82 8...

output:

954479355 885297397 66882632 523579532 685274782 377706839 512744276 949403916 635363390 473518157 927680787 767668097 667599698 778873410 261165332 455701996 542206195 187760516 400158933 218410228 996625857 111787324 99759692 373383016 181466014 291611440 453847083 819051082 826413591 123171209 19...

result:

ok 5000 numbers

Test #48:

score: 0
Accepted
time: 206ms
memory: 101908kb

input:

5000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 51 52 52 53 53 54 54 55 55 56 56 57 57 58 58 59 59 60 60 61 61 62 62 63 63 64 64 65 65 66 66 67 67 68 68 69 69 70 70 71 71 72 72 73 73 74 74 75 1 101 1...

output:

398009166 248485190 196669786 709260010 963278614 669601526 174516888 621444478 965881989 160529980 266721587 163480609 122201701 416563673 753786900 839202821 708611780 34529516 10482281 900577795 254175008 332739270 736648611 935767895 676286704 659225811 668935484 156556643 394734965 660393985 33...

result:

ok 5000 numbers

Test #49:

score: 0
Accepted
time: 194ms
memory: 101708kb

input:

5000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

output:

394377655 946329028 132923904 362760108 380155742 437962459 385548306 52896276 498712215 418720723 85031765 67743319 747154691 320711256 887422525 291315924 789521776 796034395 129851439 990992334 254124850 258945399 93255222 196409788 405504218 87836069 549136875 498349898 962637340 27851920 348181...

result:

ok 5000 numbers

Test #50:

score: 0
Accepted
time: 198ms
memory: 102008kb

input:

5000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

29961956 786182365 786182365 19427459 786182365 786182365 786182365 19427459 786182365 786182365 786182365 786182365 786182365 786182365 786182365 786182365 786182365 786182365 786182365 786182365 786182365 786182365 786182365 786182365 786182365 786182365 786182365 786182365 786182365 786182365 786...

result:

ok 5000 numbers

Test #51:

score: 0
Accepted
time: 198ms
memory: 101776kb

input:

5000
1 1 2 2 4 6 7 7 3 9 9 12 5 13 13 15 17 18 19 20 21 13 22 24 8 25 27 28 29 30 14 31 33 34 35 36 37 1 1 39 38 2 19 10 42 46 47 48 49 50 42 51 14 53 35 55 23 57 23 26 59 62 63 64 65 66 67 68 69 9 70 54 72 74 75 53 76 78 75 79 59 81 83 1 84 69 50 86 89 90 91 92 93 94 95 96 97 95 98 21 100 102 94 10...

output:

207701754 456872887 809970593 249761722 683715231 404103539 243074028 634384171 785559343 987054301 24141535 920945349 390622752 856793975 500667888 288109502 458873370 844499408 773256820 14700177 218276592 134267743 945915499 986570398 431175198 909941708 626895277 58188206 463648146 395227122 614...

result:

ok 5000 numbers