fork download
  1. program sairsodo;
  2. const MAXN=100000;
  3. type elenco = array[1..MaXN] of int64;
  4. var N,i, idmediana, idmediana1:int64;
  5. calcolacosto,calcolacosto1, altezzainiziale, altezzainiziale1:int64;
  6. costo, costo1:int64;
  7. H, ricordaltezze: elenco;
  8. Procedure scambia (var a,b: int64);
  9. var x:int64;
  10. begin
  11. x:=a;
  12. a:=b;
  13. b:=x;
  14. end;
  15. Procedure ordinamento (estremoi,estremos: int64; var v : elenco; ordinato:boolean);
  16. var inf, sup, medio:int64;
  17. pivot :int64;
  18. begin
  19. inf:=estremoi;
  20. sup:=estremos;
  21. medio:= (estremoi+estremos) div 2;
  22. pivot:=v[medio];
  23. repeat
  24. if (ordinato) then
  25. begin
  26. while (v[inf]<pivot) do inf:=inf+1;
  27. while (v[sup]>pivot) do sup:=sup-1;
  28. end;
  29. if inf<=sup then
  30. begin
  31. scambia(v[inf],v[sup]);
  32. inf:=inf+1;
  33. sup:=sup-1;
  34. end;
  35. until inf>sup;
  36. if (estremoi<sup) then ordinamento(estremoi,sup,v,ordinato);
  37. if (inf<estremos) then ordinamento(inf,estremos,v,ordinato);
  38. end;
  39.  
  40. begin
  41. readln(N);
  42. for i:=1 to N do begin read(H[i]); ricordaltezze[i]:=H[i]; end;readln;
  43. costo:=0; costo1:=0;
  44. ordinamento (1,N,H, true);
  45. if N mod 2 <>0 then
  46. begin
  47. idmediana:=(N+1) div 2;
  48. altezzainiziale:=H[idmediana]-(idmediana-1);
  49. if altezzainiziale<0 then altezzainiziale:=0;
  50. for i:=1 to N do
  51. begin
  52. calcolacosto:=(ricordaltezze[i] - (altezzainiziale +i-1));
  53. if calcolacosto<0 then calcolacosto:=-calcolacosto;
  54. costo:= costo + calcolacosto ;
  55. end;
  56. writeln(costo);
  57. end
  58. else
  59. begin
  60. idmediana:=((N div 2)+ ((N+1) div 2)) div 2;
  61. idmediana1:=idmediana+1;
  62. altezzainiziale:=H[idmediana]-(idmediana-1);
  63. altezzainiziale1:=H[idmediana1]-(idmediana1-1);
  64. if altezzainiziale<0 then altezzainiziale:=0;
  65. if altezzainiziale1<0 then altezzainiziale1:=0;
  66. for i:=1 to N do
  67. begin
  68. calcolacosto:=(ricordaltezze[i] - (altezzainiziale +i-1));
  69. if calcolacosto<0 then calcolacosto:=-calcolacosto;
  70. costo:= costo + calcolacosto ;
  71. calcolacosto1:=(ricordaltezze[i] - (altezzainiziale1 +i-1));
  72. if calcolacosto1<0 then calcolacosto1:=-calcolacosto1;
  73. costo1:= costo1 + calcolacosto1 ;
  74. end;
  75. if costo<costo1 then writeln(costo)
  76. else writeln(costo1);
  77. end;
  78.  
  79. end.
Success #stdin #stdout 0.01s 5284KB
stdin
5000
8301 4083 2274 9326 5363 537 25 2363 7028 1385 544 3954 8714 7964 1403 8414 2902 4941 5401 4149 1717 2604 3968 4279 9573 8718 322 3882 2720 820 9630 7373 4904 8256 6699 6619 8794 6724 8983 5822 4461 5879 9776 3175 3844 7531 7942 3098 2472 3343 7247 4189 5947 7567 4821 1872 6286 1495 5754 9006 2316 1737 2731 3572 9993 9431 191 5139 2507 5526 961 6969 1406 7090 6496 1602 973 4438 4700 3446 4133 8299 3987 6432 5867 5160 8305 8505 6656 411 3863 5324 8500 6594 5248 4846 2377 5439 9985 4885 966 7299 8206 8724 741 4702 326 1714 5493 1378 1512 9626 9677 1852 2411 1896 3364 716 401 20 7479 4264 1696 5980 7211 6944 826 9588 2384 7163 825 9702 4462 5383 8426 1555 6438 5104 3270 1931 6482 1134 7909 6159 2986 320 8056 6351 1036 4809 2723 4868 5426 4420 848 2637 1364 8026 8577 100 5189 5755 6154 6004 1138 932 7559 7576 6036 7181 5859 2518 8316 3769 8678 1302 4089 3086 4005 1478 7895 6729 6346 9673 7501 3546 8662 8865 1572 7240 5318 3113 9347 7824 5469 485 8757 3029 8062 4793 210 3921 7312 4878 4042 2342 6181 4484 1780 6538 2314 6027 3267 8660 5701 768 8558 4363 5986 6482 7955 7656 9595 7302 5480 5065 4140 4237 4446 8554 9031 1008 2475 2695 5887 2870 1389 8420 7354 3169 4958 9668 5548 4578 4680 7601 5346 3238 1965 7684 6072 6272 5340 5667 9927 821 7084 4067 5058 1530 2621 441 8891 1448 9488 4778 4318 877 3198 8024 398 4508 7692 5947 9086 8724 3548 4433 8314 1865 8469 4386 8138 3810 6406 8065 4631 3490 8484 6041 1373 1105 2835 264 2553 2323 5042 3224 3201 4592 1248 3599 5452 5293 9546 4539 4017 9447 5324 2332 1312 3793 6718 5802 7603 9476 219 8586 2967 8703 980 4340 9808 3815 956 8714 6138 2350 1938 9339 3294 9538 9291 8746 4831 5189 3285 8849 4636 4961 7533 2301 8755 603 4455 2710 80 4675 7649 9399 3378 8629 91 9539 2444 1047 4605 4934 9749 6543 626 3043 2433 9917 1789 7265 1458 1427 2466 6095 6388 6351 4748 1495 6954 9203 4206 3386 3878 1855 2785 3609 6836 2876 9500 9280 3923 4105 4214 3672 7000 1192 3067 9433 1109 4857 3050 2568 2636 1868 5015 9024 8219 6115 6872 5174 5318 1078 8560 5549 9285 1346 5510 6121 574 1362 1753 850 1819 2319 4522 5171 3512 3942 4604 973 5151 4007 3541 7787 5875 4908 3163 4095 7375 35 5621 9046 1113 4181 947 6750 1879 6457 2871 2454 4171 4624 3304 5990 6944 4178 1161 6808 8120 2117 7781 9623 6124 1323 7410 8352 2583 574 8799 9959 6961 4420 5357 4427 4953 6304 1177 6833 2761 401 5639 3284 5025 5295 9274 8321 9473 435 5129 3946 8904 2911 9921 1381 586 7332 9733 9521 4258 8532 5832 1219 9304 1189 5646 4257 7493 3176 1090 6606 3577 3081 9890 4954 8376 9164 3276 4202 5951 4757 4500 1208 4020 4421 2589 4606 8105 8674 480 2363 3558 6312 9935 2862 7502 5581 7119 1347 5109 4562 7954 8686 7643 7844 3641 2372 3361 3269 2926 5664 4378 7426 6872 8399 8199 5813 9357 6305 4487 9837 8668 8045 6150 4955 7259 4 537 4379 7703 1998 5293 5657 685 9288 9854 678 1660 9567 299 4586 5231 4677 8364 8456 9428 6564 4269 8786 9221 8757 8623 4241 3154 1125 9197 414 7481 6086 1145 5185 8084 6438 842 5121 2078 7048 2151 3739 6615 2450 4677 8199 3480 9394 6655 2908 2310 924 8046 1531 6033 3022 2124 5540 4147 1321 5954 7981 7407 3451 3166 1844 6241 360 6965 8319 7409 9117 8410 376 7919 9440 8575 7751 8834 5230 7012 7496 2507 5058 5379 8540 8080 7503 4080 8580 8825 6386 6561 2584 9837 9727 4428 2430 6439 7746 750 3848 3215 5512 577 1134 4952 9152 5238 138 735 2250 3986 3242 7308 9365 1782 5389 6869 2215 3969 2046 8601 530 4630 4791 6609 9059 7221 3048 6805 4323 3249 20 9836 3826 7506 1140 9330 2744 1279 65 4994 5265 3307 8655 983 1442 396 7852 3657 4365 9898 8610 1247 880 9753 4208 9939 3327 3608 3096 7650 6857 9468 3838 7035 3327 4979 2718 2423 2610 2783 7418 4227 2443 2425 5210 3885 2821 9414 3894 3538 5664 8856 1137 6545 8610 5345 2836 1937 8953 5933 5939 2163 1753 9778 5550 1432 1109 8268 3856 3719 7404 7626 4298 6199 51 5861 84 2872 1627 330 2762 7292 9186 3899 3837 7796 9244 6673 6085 4549 8958 2025 3064 7064 1803 4967 8496 9264 9587 2352 9335 6991 6330 3633 9542 6381 5846 9626 5605 7474 6308 8367 1118 5495 2266 4955 9643 7862 7980 5729 8764 3291 4106 8180 6707 2261 3147 5203 1525 2735 3908 860 6078 238 845 5621 2972 3044 1599 8577 518 4260 3297 1636 9755 5563 2943 5750 9778 7275 7831 8542 6918 1937 3074 3625 4198 6222 5181 2075 5309 9089 2935 7739 5679 133 9712 5003 3177 7664 3581 47 1924 6878 8035 1679 8793 7330 3781 8571 4605 1613 3465 7876 3550 6540 1501 4101 9114 6682 6176 775 2123 5464 8514 4155 1949 8227 9158 5126 2243 9091 1525 4167 2321 5912 2198 7467 3242 5979 2390 4199 7592 5856 2075 7495 8748 3577 1596 7862 6611 4124 8637 8735 9588 3503 9242 1537 8082 8400 3015 325 3844 892 4492 6165 6804 3042 3632 46 9022 6023 598 6614 8231 2673 461 3331 2602 2057 7545 5566 6182 2534 653 2122 6037 9895 3660 4120 4647 3027 797 8491 3920 1642 4657 724 4684 4641 7123 3706 7016 7721 6673 5247 6746 7134 8578 5701 5544 6123 1267 8078 5009 1920 200 1047 1815 212 1519 6462 3240 8668 1306 7160 310 5963 7884 4995 6956 5007 5053 3973 2728 8078 5572 5827 1565 503 1528 3461 2978 2795 1539 7988 1067 1739 9035 9234 1952 6906 2048 1544 5574 3354 8704 2237 5669 6588 3584 2626 1596 8637 6599 676 3068 8523 2855 4633 9026 4383 8094 8357 3530 5985 6345 949 4076 1732 183 2380 8638 2232 3924 564 1938 2628 2801 7608 9217 6385 234 7165 1375 3185 4193 4443 8060 7049 5428 7087 7784 9874 5444 7667 5859 8141 4968 6287 9873 5152 8668 4863 3736 2592 5427 2026 5221 4581 9634 790 7318 6220 7955 8693 9405 8500 9488 7466 1901 1268 905 6038 7494 2701 57 9705 842 5025 5993 7067 177 4661 1930 265 7253 3709 2292 2474 4642 8278 3264 1961 4499 7571 7006 3904 2424 6495 7722 4325 4115 4979 363 1610 7680 420 1315 8522 5446 7308 1941 1975 8321 3871 8593 5575 3933 7237 4401 8575 5515 4018 536 14 1589 7543 271 4013 390 7993 4691 857 2973 1406 2467 7005 8179 135 1880 9977 3795 3821 8304 2117 7693 6897 4044 7978 4134 8445 6553 6002 2463 3442 6016 405 7337 6287 770 7727 633 5461 4936 9958 6868 7404 6963 1399 3891 8843 1376 4038 9017 9680 6155 3062 2930 199 1040 3416 8645 7593 9418 7460 7387 5435 7865 4724 8074 8636 8803 5059 449 3740 5017 3669 7496 8333 5068 1387 3528 6444 5425 2545 2477 7933 5607 5407 8132 2999 8823 3129 593 8242 6942 4332 29 4807 9057 4455 9795 7860 9515 6597 1600 884 266 9096 5569 1687 483 5450 4483 2261 7995 6960 194 9955 8719 4678 2954 7543 7808 9899 2137 1102 4232 8518 5909 3289 2973 2057 7501 8840 5006 9102 6077 5272 8198 1646 3311 5034 7096 7795 3647 1444 1107 3841 1399 9827 8519 705 3722 2679 605 5859 3781 1189 4377 6043 830 3702 4452 8331 2543 9458 3785 8620 1082 1984 266 4394 3370 3715 8541 7017 5159 9648 7210 2910 5827 2081 3615 9549 1113 572 1760 1246 1761 2489 3641 8943 6192 8093 7275 8735 3903 7412 7355 4986 5748 3973 5732 9118 7688 625 2487 9199 6625 9697 2109 2453 8131 5725 8354 9244 6297 115 490 4411 2604 4132 3354 8796 8577 6981 3883 2481 4394 1238 3819 142 1564 5903 5613 9252 6528 8100 4804 3153 4150 6913 1958 8633 2638 313 7877 5288 6780 4719 9699 5736 5203 9405 885 3781 6387 4768 2614 7133 2359 6433 3627 3923 2336 9240 9527 5216 3693 683 8369 4195 7597 328 2828 235 6993 7057 5523 125 1776 1574 5861 3332 980 3098 7113 3719 7867 6079 7204 6578 2512 831 6853 1200 6424 2732 6416 117 3416 1137 664 1013 7817 3492 7600 4810 549 3124 4935 8677 1050 7149 2009 8382 247 5474 8453 4466 1553 5657 1044 417 2841 4249 7969 9265 6982 737 5734 6750 1875 6398 7763 9692 6242 5363 855 6791 4839 2142 1820 2242 5643 3830 624 5891 5656 9078 6709 7210 1087 4106 3979 3928 8355 1949 3193 1689 2686 5279 8439 4561 1677 6202 606 7919 7918 7813 1062 9109 6307 2883 1351 1951 3065 8328 4194 8721 7406 903 2283 8493 5009 6263 2422 9717 8212 1967 1406 898 7247 9846 1812 5276 2400 8770 3196 6670 2935 610 5780 9242 3493 3483 1193 2910 1811 1739 1632 9217 8995 3915 4063 356 178 2837 73 4742 4804 7832 1993 8403 4030 3805 3680 6430 8927 3228 3101 1862 3838 5233 7456 7332 8716 5002 6594 528 6741 8226 6097 5736 8494 160 6093 5024 2997 2518 9767 4154 350 1760 2557 4380 1917 6237 7163 7196 9465 6616 9058 9656 1849 6514 3340 6917 7868 9934 7445 4610 8161 9895 6698 6655 55 2791 1679 9405 1662 7798 3559 2012 9558 6116 2745 7827 8706 9908 5023 8171 2876 4081 4179 4725 6948 7519 7994 4816 7454 5440 5778 5615 1687 2477 8622 1742 1620 6653 7499 3282 4452 1058 1647 4010 3527 744 8190 2233 7004 3213 6756 9880 3647 936 4605 595 8455 2599 1763 5909 4391 3894 7876 2430 6371 6498 525 7991 3152 8024 7626 3956 9083 5625 4318 8962 6369 2508 1195 9725 5722 7951 9605 9369 5239 562 6316 3695 9513 4431 5956 257 8325 3833 2687 4696 6683 3212 9040 6187 1237 3018 143 6672 4995 4462 5634 7716 6970 3181 7441 2692 7484 7046 8413 2724 7608 1081 2771 7121 5513 5079 7378 3838 8912 66 4887 1948 9630 279 8135 867 9649 8279 3891 4644 2741 5877 2360 9711 5410 9801 8756 2895 3199 3521 1971 807 4603 1094 4280 116 6173 1659 306 5086 8077 1545 3386 7707 8176 1521 4927 7825 9800 5170 8821 2541 1048 1181 8605 6458 7334 7361 5705 6885 7234 7676 7692 1837 8770 8325 8305 4944 6336 4964 6382 4413 6509 9768 8472 4686 1289 9751 8863 7442 4922 7685 9983 2322 5218 8588 5132 8905 2301 838 5790 5888 4866 9835 7725 9989 8160 6031 4933 4496 995 7667 5261 3856 3787 85 4894 1428 9837 3758 8870 4759 7795 5206 3433 3013 146 8565 8270 8800 9403 4061 4688 622 248 2413 611 8408 4796 1896 9256 2143 9563 869 2352 9702 954 7246 7482 791 7356 2705 1902 5151 7911 5335 4517 4409 3901 2787 3209 9656 6848 7897 278 7096 6663 7241 1856 7811 9137 7464 6307 5052 8333 8659 4754 9288 2257 8589 6431 5966 1294 8334 1117 9205 3669 5634 3614 3922 4774 3176 9931 1622 7425 209 5071 4088 7451 3279 8252 2940 744 911 7993 5429 5922 2747 1069 8179 1336 7501 4145 2630 5835 1615 8187 5856 3601 8154 9779 8375 1330 9710 6350 8755 6271 1421 9196 74 1052 7448 3015 8148 8359 1008 3578 4281 107 4647 8812 7796 2148 9310 6778 4335 925 1318 192 878 9472 6323 9254 7154 6033 5604 5909 8656 3377 1457 5083 781 5257 8098 8930 9968 5458 8860 601 1917 3507 9414 9713 2008 5076 2844 6343 2353 4162 2887 3231 3634 9210 2485 788 1595 4441 3049 252 4170 4507 1687 4952 6116 9785 3882 6085 1595 2742 6686 3512 2601 2452 9578 4609 7528 2422 7305 9881 6584 192 9465 6570 5755 1950 3710 7350 2744 3111 3954 6914 3970 5641 1866 87 1778 2100 6172 3373 4842 2858 3238 3796 5311 9168 8405 9191 1590 2062 9073 4526 8607 8538 7448 4362 6840 7510 8064 5936 621 2019 9203 944 7660 1069 1031 5791 9522 3555 9164 716 6413 8754 4512 8076 7922 9270 3620 5864 1332 2693 6742 9939 7583 542 653 775 8052 8718 3064 5026 737 2267 5970 4749 9688 7001 540 9210 556 6057 9927 3321 4811 791 7750 9086 61 1370 1302 1394 415 8045 7685 4350 4939 8339 1477 2992 7057 4541 8018 4146 3160 3988 8895 2849 7341 9436 8411 4249 1845 4690 3922 6656 5482 1672 2094 5543 9394 3397 6937 9809 7794 975 511 2733 9314 1989 2077 2723 2882 95 6869 2395 435 2116 5244 4128 7904 7 8377 9749 4698 8652 2758 6532 324 4852 2075 9719 4601 5365 5880 8747 6340 2744 7833 2006 1085 9910 4729 3967 6358 7950 6362 3145 66 7958 7274 7971 4318 2003 7720 9016 655 6830 1900 7332 1683 327 3403 2636 5692 5635 1384 8384 8379 9217 6742 9464 5479 1471 9784 1837 5773 2498 4983 5840 457 8609 3811 4775 6964 7883 143 3972 4714 8395 1304 2749 8722 1059 1737 767 6694 9473 9151 5074 5042 2246 890 522 69 674 8711 5843 3173 46 1683 9982 8655 1846 4757 1972 6081 1252 5944 7147 9647 3600 6248 4721 4659 7986 5488 1353 3811 4640 2779 8854 3238 3670 5728 3307 4344 4439 9150 7517 4486 7185 3851 9493 9031 4960 1465 1465 6212 3761 4964 2211 7361 1213 6933 2020 5551 8773 3374 9362 9765 6153 4568 3003 9823 296 6311 520 1088 5461 4389 1926 2647 8241 7771 8030 3201 5589 5847 5766 9350 812 4329 6712 2025 7614 5084 3928 6388 8458 3290 6153 964 7859 9157 7139 4507 5468 4011 1947 7281 8401 225 6280 6642 7997 4311 6195 3586 6510 8313 9288 7322 2643 6000 5699 257 1085 9627 2997 5895 9270 9151 3211 7129 8308 351 7988 128 4362 6288 7409 9115 6513 3690 2109 4510 4353 8305 4448 7215 2970 3737 4538 5613 6089 6589 2223 3526 6217 5220 9422 5487 723 2633 8968 5383 9336 3308 5511 51 9596 9273 9166 6110 9315 1276 6972 20 5933 1421 7235 8903 5158 8125 869 7599 4715 3092 1126 7284 4664 548 2771 1740 9533 8091 7123 5222 7751 8987 5273 7348 8260 791 3458 3927 2067 430 3947 4352 8203 1182 3256 9713 5660 477 7313 375 9921 8439 7659 4585 5339 6782 2677 1224 1225 9801 6446 8976 8788 8071 6324 3400 8863 6134 3679 7282 2917 7626 1635 1120 5160 1243 834 820 1720 8147 1195 1641 2938 5206 2578 8277 8340 5256 5853 9565 1409 2300 8542 6549 6723 1218 6301 5586 7353 9980 9221 270 7606 7208 7742 9118 8451 8576 6291 6523 3075 3838 4516 6013 9045 3446 642 7385 5054 6496 3303 6463 5148 1845 3012 8223 3063 5665 3810 6768 5645 9383 3390 9603 6591 1133 8722 5042 6061 5013 7917 9137 8851 2433 1502 4248 5879 8497 7986 934 1345 1289 3749 2845 3134 3114 1068 2549 8779 1230 5670 4425 613 9060 380 7204 6545 9102 8598 2607 467 6515 8096 5671 5300 5950 9919 7532 799 4257 4818 2144 5546 8567 1341 8680 8033 2410 7582 6813 9992 3252 7590 606 8664 7970 4162 5210 3425 2761 4169 244 5628 8617 5915 7281 4567 2187 4813 5367 6444 5983 3863 1991 4550 5205 7023 2584 3967 957 5749 3959 561 3339 4565 9226 7661 5080 788 1086 4193 1309 1331 9821 9926 3598 3454 4493 5785 4619 6212 8582 602 6428 6925 5153 1633 300 4089 5600 1258 6190 5911 1819 5881 6829 7397 3542 1909 4537 4629 6102 5846 2312 2275 5772 5910 5730 6618 8048 349 9182 6630 952 5610 9907 2457 7243 207 2898 9195 1465 9088 1459 9637 4969 8288 7034 4863 197 1572 9492 6299 3770 1804 4926 9543 4067 656 2513 2115 7358 1695 5097 8310 7306 5004 7119 901 5211 17 6449 3029 5457 7908 2666 6778 6196 6052 1641 2745 3976 7486 5396 7747 5642 322 7290 9709 979 9803 8176 4689 7850 3273 2999 1508 4629 6470 2410 6193 2839 5211 9222 8296 3119 8240 1426 5667 4292 9419 8412 8269 6905 3808 2368 8900 4130 9658 4961 1461 5813 3138 6150 15 2763 5501 1524 7393 1971 286 9938 4810 5497 9160 9458 8616 7400 7236 4283 8044 6656 2695 2665 9913 2855 5033 8813 6985 1043 127 4799 3208 3265 949 3224 2380 6451 1100 6125 4774 1386 6063 9585 6883 5223 5395 1851 8975 2632 6134 3372 5640 5181 2389 5553 8036 7423 719 1373 4818 846 6172 4379 463 7122 3955 2843 9925 5055 8969 4699 6441 5032 636 9676 6608 6032 1527 1935 5016 4013 1659 656 9194 4049 2561 3582 1472 3280 1307 2642 4126 7480 7021 941 954 976 3785 7231 6031 9106 1930 8824 490 8919 4852 7098 4951 6379 5386 6319 6744 7045 6975 2290 1094 9536 5872 8918 9169 3532 1561 9647 1012 8582 589 8318 5911 4374 5549 8294 9832 3831 7119 322 2750 8323 3773 4053 4703 9159 6724 1447 2556 3699 90 3 9588 5962 8921 8757 5846 6834 8404 6858 1769 8993 1528 7680 9719 3429 5974 9551 7261 9445 6226 6363 7769 9999 6769 8824 5510 3493 6623 8066 3545 6713 8069 9485 9028 3343 8242 4874 177 2998 8085 1946 8344 9613 9626 4415 3043 1953 319 6656 1398 6545 9371 5519 2896 2492 4343 8406 2338 7319 2824 5883 4032 894 1720 3060 589 9962 4287 766 9312 2372 9065 7656 8337 8691 2072 7732 6996 8743 4388 8395 5288 112 266 8184 2604 4610 6590 4942 1929 5766 7177 2313 3012 8897 1726 3601 5211 6013 4368 4524 4737 3433 8532 9426 8476 604 7159 5473 5699 7899 220 987 8011 6838 5523 6968 1448 8465 1910 9729 4232 9088 8395 7244 4337 121 846 9549 2486 1566 4073 3575 1351 2605 3001 6179 9562 160 8004 5261 4412 4576 2601 8775 1415 8124 5743 9215 6590 4006 8945 822 9446 3692 4418 3783 3813 5264 3332 2651 3182 3757 6226 885 2715 5579 7065 8629 5740 1421 242 6504 5998 2843 5279 7413 7320 1023 6628 3910 5029 1925 1084 4475 5617 1854 4610 5782 3471 7943 4785 6653 8052 7363 7539 767 2943 956 9396 8683 2377 9639 1539 8375 8834 6818 2140 6154 4193 8769 6416 5574 7046 7500 6401 9016 5707 1012 1150 9178 5307 5936 5831 3359 3299 9722 4127 6242 7030 9875 1277 9408 5866 9168 4135 4701 5987 6276 855 6532 1397 7272 2107 4795 1124 8508 3811 6831 5872 1314 2361 1179 7250 8193 4539 6901 4267 5018 9496 1298 4893 7125 706 7112 6294 1193 1813 8633 3821 9020 5165 1570 2644 7272 6366 3769 2133 6529 6952 8005 7843 9314 5537 1445 3859 76 4699 8126 1446 4195 9424 6339 7672 6482 9803 3966 4028 1616 2599 7849 637 7765 9420 3281 1389 2138 3402 9874 5019 6707 4232 9215 2373 9769 660 6232 6197 1711 710 7643 5906 6487 334 9931 9321 138 3897 3349 1754 2849 7551 8743 6966 3323 8377 4707 1813 1779 4582 6832 4838 5166 6047 7211 4935 3060 9795 1132 4771 6858 8775 7030 3345 9109 6961 9018 5599 7210 2368 3706 59 6271 2449 7025 9594 826 1733 1407 8958 2667 4591 148 7833 639 3712 9120 51 3507 252 4822 365 5379 8204 62 840 1517 9081 6440 8728 7801 146 8787 4072 8947 2165 18 6126 250 7777 1436 2917 2368 1584 750 9359 5296 9870 9410 8804 6474 585 5521 8205 5141 5584 9045 6659 4665 1837 5387 2466 8335 526 2890 7283 2691 2908 3409 2941 685 4845 2210 9405 2781 9312 8765 8078 5534 4527 3234 8360 1464 5107 6565 6606 691 5611 3265 1708 3800 5004 526 2136 1882 3416 9419 4574 2676 9180 3867 9713 4025 2430 9119 6806 1742 4236 1236 7277 8763 4470 5637 228 9578 8555 3186 6621 518 2803 4682 4318 7807 1560 6454 9689 1329 2225 615 4005 1405 835 3719 1782 3265 2838 4941 1359 3426 6177 4988 2189 7000 6978 8769 6578 5533 8307 9551 6051 1110 4233 6721 5269 2146 3176 4959 3475 1753 1926 7480 3159 9113 7551 1293 8730 6741 6234 90 167 2412 5078 2357 9412 8408 7478 2342 3941 5786 8245 6344 6896 8831 3066 2166 977 2594 3477 4452 4347 1755 1932 3858 869 9484 5152 5951 2577 1386 6041 2745 150 7472 1454 5914 5880 8932 8256 6174 4718 6502 2518 7967 1685 1936 6485 2662 4530 6314 7114 5230 4421 5398 9088 5290 1234 592 7594 3812 8331 3635 6557 8481 7459 8011 4396 9692 3295 9004 2218 4366 1858 4736 8685 3543 3025 5170 6205 7555 7836 9671 9137 2257 1422 4578 3900 2656 5170 1494 2820 3501 1481 9377 8335 8941 3740 9083 4985 3388 8087 7203 7754 6298 8291 6439 9841 1316 7961 2399 5224 5797 8422 4361 8054 9844 8939 1954 2501 462 9800 5321 315 1282 1051 8650 6575 1143 4085 1560 4531 8525 8763 8637 4823 3406 1428 1016 1075 9389 3415 6299 1538 1838 7012 5945 1682 2304 4251 535 9118 4052 5857 9433 5334 3260 4436 1909 4403 8521 9821 5287 7046 8584 276 8221 8342 1705 9238 9417 7446 2653 2068 5337 843 9081 1282 2526 7737 5533 9413 6855 5937 5270 6288 1271 4882 724 9532 5638 5598 9353 7277 8996 4289 7553 7218 2632 5610 6456 2049 3057 5461 470 8394 6305 9551 6028 5183 3640 7913 4596 495 3851 6219 3135 5122 1101 212 1007 6739 5810 360 4016 4806 1002 7922 8376 3634 3532 4832 2035 6589 294 2505 1335 6599 8408 3715 8134 2048 1629 2730 2543 5480 8949 2031 6954 51 2243 7961 3142 4405 4674 3511 9211 5676 1433 3940 5662 4965 8772 7697 7907 5418 6555 5594 8369 1315 9310 6503 3364 7291 9234 2259 2771 8183 4290 6077 4586 2885 391 4081 7290 5065 7592 2854 7093 5377 6794 2755 6694 1918 6804 4601 7337 3359 6548 2058 4675 2210 8562 4391 9501 4148 3002 8624 8683 7293 4701 9622 178 1444 3703 3821 6509 1295 6675 3602 6672 3469 2709 3366 5387 9514 4320 9076 2873 7220 1135 3900 9430 6049 4643 5283 6549 7646 259 5232 1291 1312 4854 7821 2757 4909 1642 9266 6204 8317 9221 9228 8138 1930 2595 9878 1444 3267 8954 670 487 6441 922 6269 8842 5566 7904 1743 9564 8163 3328 855 9475 8182 8676 8584 3092 6671 4203 5648 1340 3424 4877 9479 1706 3824 9357 9503 3443 4663 173 3930 7457 7447 6551 2651 9365 807 4395 8929 8970 7723 6136 4797 2257 1165 3382 1701 7836 7585 3702 9176 7361 8579 5007 5419 8755 4364 4922 2198 5380 1447 2480 9189 8895 5383 1840 4612 6190 2587 9894 1512 6662 6030 6309 8920 7195 6043 6973 1383 9980 675 6912 3693 5606 1919 9113 4361 2636 4035 2911 8016 1835 1743 7205 7082 7126 5397 1694 3316 4337 1588 1180 999 3971 7490 9919 7518 9885 3245 8902 6218 3920 2166 9911 9527 4085 5376 240 6721 5764 9504 1089 7599 1247 4646 4681 8374 6396 6375 8042 733 4316 9223 1732 4639 3065 8004 2157 9302 1249 7411 5520 5169 9577 1784 1048 15 7160 7641 3088 2924 7145 4178 6875 8392 5176 1556 3118 1572 4284 7513 2305 4952 3088 390 9591 2505 8394 8100 8159 9643 5512 3680 1164 1441 1816 8565 1456 8976 6206 897 8253 9703 5075 5128 4447 251 3037 7566 1824 7321 1431 481 2273 871 871 8216 3376 9265 6316 1535 5260 8180 1567 2777 5974 9735 1342 3782 8712 3900 4679 3317 3603 9754 4797 8050 6358 7834 1968 4534 1507 9751 5015 132 622 2239 8348 350 7856 1017 8238 3117 9197 9805 2246 5171 9541 3588 8954 4605 3840 9985 4274 3795 9740 9071 1845 2450 6906 166 6984 4765 9917 8351 4898 540 590 3246 7242 8447 615 5480 7916 9813 1638 162 1336 7531 102 6642 8488 3942 6628 2762 7737 2720 8185 5934 5170 1443 2452 8506 6209 2370 3209 1107 9262 152 705 6504 8599 1321 8337 2867 7486 9975 9381 8822 7506 9483 1817 2346 9777 8445 5108 3866 7517 9645 9800 2687 1089 2253 7545 7298 975 754 4757 6589 906 5462 3093 5857 6783 7782 5076 621 7757 4457 9444 1615 3940 7613 3961 3717 6058 5421 7583 9927 5067 3736 2614 6156 2341 6511 9806 3316 7265 4563 6257 4524 6377 9350 381 9513 7133 5458 134 1242 9915 5930 9210 208 3543 3171 277 5953 4945 4213 5880 6364 7949 4846 2520 6642 1357 8678 9958 8623 9593 2567 3147 5970 1917 9880 5483 5402 1690 5618 2997 7958 1548 2207 8166 5092 1730 8443 7397 3027 2656 3278 9391 6957 8124 8263 3599 9482 6941 9909 4457 6534 2476 3956 8857 746 3836 4340 6148 5527 6310 5497 3485 4211 4056 8003 9303 5787 6446 6700 5166 5455 6330 4558 2412 4455 2821 6012 3937 9763 5921 8394 2649 4750 2350 1506 5496 2538 2199 7996 4417 8509 3494 4254 2720 7550 2257 8375 9689 5056 1428 4856 511 7758 5766 9275 8565 8587 5287 2502 8350 7561 7248 7352 2311 5950 5210 7807 4841 7409 5803 9258 2271 5649 3513 1343 9552 2122 6071 5593 3530 3851 6801 4041 7961 2567 9669 6527 1155 4956 5381 5857 8869 8982 3209 7532 4932 8420 5339 9773 2181 7495 5384 804 9496 5249 2148 5400 7371 8219 994 902 8422 7795 1295 6383 363 964 2910 7870 2273 4644 3727 7494 3626 3289 5027 4910 8061 6718 1036 6594 565 6420 7399 62 1669 9547 5462 5392 4118 2808 2646 2540 604 294 8923 7319 7610 8186 5189 9883 2830 5268 7378 6456 4909 2405 7718 2970 9123 8754 9565 9689 1526 6964 6103 9547 2863 7917 4940 3333 726 3938 5873 1330 4232 1148 5001 8195 9334 6542 8078 2164 1810 1808 4972 6720 4213 9043 6042 9689 7797 1959 5730 9324 5275 8185 5223 8138 6102 6515 1471 6828 454 3696 4510 1038 4845 9511 9233 4179 2405 3664 2696 4216 5472 4020 7288 6038 9415 9682 2079 7213 7994 4161 2889 3269 2346 8112 7760 8448 4628 5583 1629 1434 9280 2491 8824 477 2003 8058 1008 760 8074 56 4976 3546 4077 8616 9584 3492 4651 8015 7057 2645 2176 6298 5914 4522 763 26 9323 1743 5610 7304 3177 1242 9795 2001 1719 8150 6411 9079 8911 4485 9136 239 4384 9565 5208 320 9409 9859 8336 2819 8856 512 9117 1122 1387 9880 1149 7062 7975 3111 4366 1152 4353 513 9506 2424 8664 2269 1503 3927 6755 6991 518 1139 6556 5726 1459 5966 1937 6147 8785 793 6660 4254 1916 4399 487 9417 1461 8462 2528 2179 5967 3233 2692 1825 2009 7708 4094 9864 7987 849 6856 8506 8340 3412 584 6152 5730 2522 2299 867 9667 5311 5122 7935 9710 1961 7352 7523 423 6232 9702 2742 5817 8747 4567 7826 2807 8662 7691 795 5863 899 9301 4204 4311 6237 6708 6394 8759 9007 3613 4779 671 5087 2714 381 7048 6419 4257 3824 9003 3959 6566 4821 9058 1134 2647 1866 6148 6690 2661 2011 7589 8314 2567 8253 4551 9275 999 9663 4635 4612 794 5306 9700 3508 2039 6748 6279 6296 6924 5283 6608 3491 6456 5666 977 9103 7532 7125 2146 193 5488 9735 4859 4408 4340 5763 3683 5339 5426 4670 9952 6220 6328 9652 6080 8368 2752 8712 1016 9677 347 7624 9520 6803 3291 6849 2258 7175 326 4404 3721 5814 492 8580 222 4832 4343 258 172 6121 1280 6476 2341 7609 6128 4774 2329 5232 3486 9697 1261 3833 7322 781 6988 6965 7630 9246 492 4308 3 4213 123 495 2794 6697 1679 3489 3307 1851 9611 4588 8327 8304 8549 807 3078 7230 2392 2916 6927 3653 3101 601 787 89 7566 4769 5688 8059 9078 5691 2272 5553 6186 1418 2250 4217 4908 1910 6069 871 2850 748 9175 1399 7908 8606 4981 300 1522 1908 305 976 2510 1092 1065 6428 5862 6753 839 1292 8796 9464 6845 1334 882 5447 5552 2142 7357 7973 3013 207 8721 8541 7958 6629 7147 9291 3281 8669 1200 3587 5997 62 4679 7063 6490 6893 168 3682 4537 8965 3146 1382 6651 380 6830 2203 2523 539 176 1888 7099 5250 429 5057 1879 3928 4349 5161 8950 1901 8748 4947 1963 9779 2010 4805 3025 8531 8487 7562 3848 7985 5297 499 8366 8479 9055 7241 9018 9231 9129 6117 4481 5911 7527 2713 9839 8228 7874 8789 6481 2974 3737 4796 9105 2099 9601 2130 6982 4441 6045 830 2426 1342 7682 7144 9821 6737 4385 5191 5968 9867 1309 6802 5778 5188 9515 1969 3416 3741 7111 9897 3067 7200 4693 2172 9299 646 655 2634 1439 3052 3464 218 746 1146 7362 567 7883 8100 5758 204 7967 3419 7006 3745 4959 2873 2066 8375 6614 9177 4624 6033 6377 5669 4557 2029 2668 1564 4663 4107 4616 4479 677 5362 5626 4392 2281 9861 2492 4392 6417 459 7811 9775 556 2771 2648 2622 7498 5614 1800 8475 1647 8177 496 6205 6558 3164 7769 1221 3624 8738 5701 4301 4100 7679 8693 6382 3892 7537 7126 310 7996 4937 85 8552 4060 9086 1175 7911 4700 9327 2738 2700 3856 3234 5257 415 2751 3026 7988 6375 8116 3689 7028 2217 7720 2074 4951 1613 9611 2077 1923 3960 3366 8360 




stdout
13383110