| Ticket | 13550 |
| Problem | 1695 -d1 |
Unable to dry run this testcase?
Try making a new request with small values of n_high, t_high, *_high, etc.
1 2000 1877 644 668 628 162 1136 765 1059 1347 424 178 1381 696 1271 1580 1518 1879 191 1882 1733 1536 640 1328 1664 1751 847 1534 1838 531 27 33 501 305 1571 439 405 793 103 959 1330 1941 478 145 1846 745 1764 1289 1682 1697 312 1919 860 1701 989 1079 1240 1776 1913 1274 791 1626 736 1719 124 877 1138 1459 1595 1060 1427 1111 1283 486 880 1785 1557 364 1312 1477 1465 1452 338 1732 565 1294 1026 741 785 1787 54 1729 1192 156 407 1254 1017 778 1500 60 1573 1128 1410 56 14 454 748 448 1784 967 1491 454 166 345 1396 877 1389 1350 1183 1020 730 1564 1390 494 1889 631 1299 1291 1918 901 1100 1259 740 965 109 236 281 1117 859 704 810 1122 727 776 1171 328 460 1368 384 421 561 1585 44 1977 478 1580 630 1365 1191 1984 804 1330 245 978 1221 1584 138 282 1095 318 1274 1508 498 1486 609 1659 1036 67 51 962 622 178 93 1642 675 922 610 895 1067 850 433 77 879 132 1273 1974 1149 1221 1814 120 1318 1195 1077 1653 1304 68 530 1719 1322 1570 785 591 1562 699 801 272 1908 861 364 529 468 933 828 281 1865 1192 1220 1568 1119 597 1981 654 1341 276 633 1871 509 1373 1805 16 1724 638 110 1714 1663 1135 412 102 157 1176 1697 976 1713 1734 1489 1598 1728 89 1896 1212 251 925 1598 1146 1695 1367 32 1736 880 1299 720 914 1838 172 1698 267 786 835 1182 961 1825 878 1612 1927 946 539 704 1675 590 1780 272 857 184 1419 1830 1056 962 1959 1123 1812 1317 1111 1520 880 1647 1220 1324 1198 919 245 680 484 948 1513 1182 1316 899 33 98 1604 9 426 1622 203 978 1872 961 254 824 375 937 1973 235 259 876 992 66 559 567 873 1822 1230 690 244 688 272 1975 704 1546 1457 1978 1808 429 1438 1111 1683 574 62 827 1923 1615 48 732 1630 1576 670 939 1670 146 245 466 1695 1274 1420 179 1996 164 1297 1219 1487 1635 678 743 1881 1049 198 1416 1523 1743 1602 154 1499 1232 605 1923 1540 274 325 1612 444 1797 646 1696 719 398 1383 697 318 1981 1913 1083 1650 1284 1717 7 1334 1766 1564 176 665 1444 434 43 936 1909 759 1926 1934 1401 1081 1396 483 1289 500 1403 590 1885 1748 1250 266 1035 1086 754 1383 1679 1322 1253 554 138 1041 1821 574 1205 901 712 225 1466 1208 979 1697 1081 298 1710 437 564 949 1634 1875 704 1833 389 619 1004 477 679 1628 768 1421 897 1798 332 940 455 1181 1645 429 449 165 1578 1226 1946 1162 912 1687 707 868 343 576 676 403 774 307 840 635 257 1214 1655 887 479 1952 401 929 1125 208 931 964 1961 822 1401 1182 1039 1258 1651 1969 822 1377 890 1505 348 1831 1985 1297 635 1163 256 101 563 841 1320 1722 222 1194 925 814 874 1530 1923 1282 1623 935 1630 1573 1556 1192 163 594 261 701 1030 928 1613 1947 1858 1249 5 57 1845 1337 634 1274 150 1654 506 389 730 70 881 175 963 702 1050 67 673 1837 862 645 772 475 835 159 154 8 235 1942 1990 1819 183 426 477 713 839 498 1626 636 241 1889 1028 1550 1375 922 1857 629 180 307 1115 289 326 1695 1544 1939 1503 1795 1456 1979 925 426 1498 450 1858 1145 147 1 1559 804 1250 879 702 22 1026 911 316 885 202 1594 508 1172 1204 565 553 738 1786 1888 768 1730 683 152 1393 1928 1292 38 1107 1854 1757 1006 120 698 1604 1686 472 1225 963 1411 1750 172 1015 603 987 768 505 883 1812 366 847 116 1832 1736 718 1019 1251 1479 1845 594 888 8 1338 559 1245 764 475 1912 651 1681 851 1593 214 1335 401 1731 741 1593 121 690 1734 1628 1379 178 886 852 685 110 1103 113 642 1955 1966 138 1828 190 642 1907 1748 1629 1323 714 1930 374 1851 388 1858 1068 1453 1131 427 207 425 969 364 1090 100 1039 625 810 829 211 164 1954 365 278 783 655 1742 149 1848 112 1150 4 904 1676 1910 1522 883 980 770 270 57 1377 308 671 589 533 965 1353 554 711 1802 77 1429 1167 1853 798 1610 595 808 1203 1379 876 1603 1259 1833 1074 875 1565 187 89 596 1373 1809 1951 780 1656 1619 1869 491 1697 1740 1718 550 236 1419 45 1562 1427 1858 1075 1142 876 480 401 44 66 1883 1387 560 1184 1519 402 1294 1635 1859 561 1575 1147 1666 1664 1818 1093 197 1633 483 441 1706 1738 383 836 155 642 1723 1119 708 593 1088 1902 904 1142 1227 165 1811 1289 1433 1340 1168 1878 1688 338 422 31 608 1506 1023 1610 126 1626 423 1152 854 434 1626 1490 1889 54 880 1949 1948 215 555 1206 2 870 1702 1469 1458 1953 1558 1158 1534 324 450 1487 567 291 1905 1466 1112 1862 325 1063 1526 58 76 361 1347 1154 1751 1363 1814 517 1416 1318 90 130 8 432 1181 1612 228 93 23 1279 694 862 60 783 919 1927 1694 835 1713 1582 1380 1417 969 1986 1894 1045 990 189 1333 1667 905 1932 1187 1016 1269 1411 960 1992 1274 891 892 707 1362 1574 562 758 1251 929 906 697 349 1628 65 1831 879 812 747 1982 572 1702 1224 1796 95 300 1040 1715 1704 888 289 38 265 1772 185 164 1166 1973 895 471 990 300 1221 1933 1213 741 641 28 1914 1894 1252 224 327 1094 1318 1105 664 357 213 666 976 1906 1373 1112 1322 968 725 1276 1694 208 90 255 1084 517 1202 1728 1881 1735 884 869 376 1332 823 1267 804 443 92 745 1114 377 1885 1759 1975 1377 1598 1134 65 33 399 219 104 1247 423 266 1597 1340 136 401 778 89 1501 1177 1718 943 1739 855 788 1608 1392 1652 1932 992 1591 1728 631 1209 1566 1256 1488 1258 1957 1982 1778 1512 216 1103 907 618 1532 880 734 87 1824 1104 1277 1547 1422 81 1982 980 1760 533 412 272 242 1446 608 844 767 808 1025 77 1279 1978 572 968 1593 524 1073 1313 1221 1952 2000 1438 657 890 46 976 1818 1281 1038 1432 1026 1311 1823 206 532 929 333 207 620 749 1045 1125 1480 1493 52 517 1258 339 233 1416 1714 755 1501 76 1629 1918 959 88 926 682 138 444 547 1164 441 45 1516 1674 602 1654 144 588 1080 1041 1771 868 356 1447 688 414 1994 1622 234 1304 414 956 1067 134 1753 916 683 789 1346 85 836 883 1228 1501 1161 1739 1551 1658 1998 1091 596 677 1572 569 376 1223 1686 1646 845 1529 1415 868 1869 1562 830 1371 1549 209 753 199 1736 600 1963 876 510 717 1801 1841 992 1502 1431 1438 239 584 452 746 1323 788 1245 688 1235 698 1804 271 1080 1873 896 386 685 1276 25 1715 689 966 418 81 1077 685 1548 1425 864 1579 883 1473 1824 1001 671 1868 262 1668 853 1377 1644 1870 332 602 1233 453 1327 1511 1301 1504 325 1533 308 1341 1129 672 1353 590 1098 570 522 1676 1840 1855 1186 875 1943 9 1441 1268 1486 561 378 523 1509 1927 1495 1893 1620 391 1754 1547 762 777 165 574 850 344 744 459 1780 1344 1604 1724 1092 1654 865 1467 57 456 1811 1423 1072 1338 941 861 1754 750 1998 1524 811 1218 1920 995 945 1299 1880 1246 387 392 83 70 363 1890 1777 344 1260 1588 1763 180 392 1236 100 603 1874 1383 95 1706 177 1881 1692 1250 1775 1937 1150 1284 1450 90 1812 1587 1384 1442 802 200 1114 1812 1646 262 1831 702 1093 1990 81 994 1322 314 837 584 1322 1395 260 220 1216 976 1520 693 1249 573 1348 193 1434 284 348 783 1209 914 1013 249 643 247 1503 1300 326 87 953 1447 1956 537 1737 1835 468 461 1053 890 1319 1161 999 328 1525 1915 1738 167 1218 111 1278 318 1610 121 106 346 933 1196 1081 1494 752 4 1455 1350 880 1978 306 1816 836 269 1577 68 375 127 1892 1619 652 168 564 638 1577 1144 1126 246 732 404 1391 1101 497 848 1871 322 1496 1677 662 551 30 1435 1055 689 1958 1431 272 1245 1033 122 863 1947 436 978 752 1088 1370 22 1607 1157 252 363 1292 630 219 744 279 169 811 790 1738 1417 424 811 1549 1259 1318 1163 300 1612 429 612 1550 1369 1227 1376 1598 1108 1873 1385 454 986 1453 877 114 1832 1419 1952 294 1658 1049 1071 1546 1169 920 997 1491 135 1866 683 353 1414 1192 1876 273 1444 855 73 1271 1325 132 145 1284 1274 1881 938 654 1053 1349 160 737 154 1593 695 413 1337 1339 307 945 1893 2 485 323 563 337 475 864 1511 318 1662 1822 1144 441 1590 726 874 784 847 946 40 1984 915 1667 681 1373 1822 1964 1890 1325 1184 1281 1656 1159 704 1885 1047 27 264 771 764 1878 559 414 1353 514 601 894 990 687 395 995 99 373 1648 330 923 1612 810 1766 921 1726 1853 1110 1811 776 251 1612 49 466 1870 309 1830 416 138 631 253 314 1884 407 1604 1133 1594 1458 1543 1712 447 1383 1492 1903 1664 343 475 834 369 883 474 1654 484 1207 242 409 719 629 1917 1156 1443 390 454 319 1643 307 1122 1010 1526 1982 698 1903 1439 1925 867 1591 1862 637 662 1218 862 462 211 1581 623 1727 1367 950 427 300 4 1193 1680 1614 252 1695 642 1670 1594 1639 1208 36 1331 611 1568 506 776 893 522 704 1501 1018 1337 952 473 1881 1357 288 1499 335 992 648 1051 100 891 1624 1706 1211 1120 1558 541 604 1374 811 1760 640 1991 565 1016 13 1990 1217 902 690 493 607 459 1962 1318 1838 1045 1191 556 575 84 1887 405 1435 1685 1318 1174 584 1708 490 251 1899 716 574 1127 770 1715 440 992 122 1993 1088 1872 292 680 1095 1612 267 561 978 145 816 42 1785 1416 1765 65 957 143 1044 119 1313 1411 1621 777 742 1036 125 917 920 214 1987 100 1434 28 1182 1266 1556 745 1242 1807 74 895 211 1954 1950 221 1579 882 1342 732 794 1721 710 799 1844 1182 1580 496 1323 31 1884 1454 1887 854 1818 1466 305 1041 1938 1783 1483 1326 1519 788 201 998 1835 1747 627 1873 579 667 1719 789 1465 1783 686 1733 13 542 872 515 406 582 585 1764 1542 1477 1097 821 703 1474 1272 654 212 285 121 817 1033 1775 1806 1752 1103 1145 1278 1858 1801 715 1818 1794 1920 251 1314 1470 138 1604 1598 367 513 541 1318 1916 401 1216 656 1705 1419 732 329 1007 1671 946 1222 1980 555 1968 633 1513 314 1921 716 1681 967 1573 962 1055 287 74 559 1517 1999 824 1397 173 573 1715 243 27 1079 1168 41 1507 726 381 1776 1683 1617 1357 308 332 1738 1254 1186 440 1840 238 1347 1377 401 1559 1241 181 1680 683 1305 548 1768 21 57 647 1056 824 646 1769 301 778 901 2 1719 1186 1419 1638 1903 1097 1046 733 430 1663 237 1782 1445 1740 587 1944 1666 1141 307 807 161 741 958 509 142 888 1784 1997 1648 568 1658 1500 1611 613 875 976 959 813 1885 879 1388 968 551 460 196 1475 275 1275 1534 1553 1279 33 856 318 453 1427 854 689 1764 420 382 562 296 1423 1612 258 486 1367 1127 1535 134 1657 1803 627 218 1666 296 1345 1390 1711 895 1528 1588 1940 688 1764 1517 1867 529 327 649 22 1834 1318 1399 315 26 397 1595 557 903 1902 701 578 1970 277 1800 520 1124 1297 1817 1081 192 1965 1213 603 1096 1244 911 506 606 165 1707 1069 210 1766 1027 317 192 1664 1277 1623 1626 944 359 16 898 90 1186 88 1454 1954 1248 1219 536 267 1609 1168 1747 1906 793 194 875 1313 1136 729 1318 251 1897 412 1126 242 1112 1412 920 64 179 158 1790 1306 573 450 1769 1549 1378 1076 1706 112 1281 382 699 1880 264 1749 1490 1424 1542 1394 1008 170 1441 805 1618 1732 756 614 1476 1640 678 909 1398 921 1436 1579 17 483 283 669 1713 1949 1209 825 85 483 1377 1265 354 843 1618 1665 37 952 864 1068 1050 113 355 918 473 1773 1448 1333 90 763 733 464 1454 1278 1153 1486 710 1123 508 1912 1715 1182 1550 1997 1649 642 935 124 1058 1973 564 939 880 295 414 812 1880 1003 1301 1923 1799 846 1779 996 1827 1166 984 1361 1042 497 948 519 497 1918 534 1364 524 1412 331 1572 1070 1256 1663 1449 663 1055 947 1021 1117 1917 836 1452 53 1737 1715 1452 731 645 29 405 1225 174 1561 1589 1962 1083 936 90 279 1554 1395 1926 1598 449 761 487 891 273 453 1745 543 1564 690 1582 1128 1709 1977 1213 1862 443 1354 1564 1748 1274 70 843 1414 1971 1740 1472 96 1891 1851 800 1144 594 1496 361 621 1922 1669 351 897 1863 836 785 887 973 180 693 629 419 1703 1567 1212 135 490 1670 1515 1539 769 1405 1320 793 204 1026 1044 794 1668 1713 1935 148 913 1026 1355 1578 924 250 925 1560 983 985 1049 760 1115 867 882 69 1548 28 1248 637 72 63 1818 1333 743 1504 1969 1758 81 12 1707 195 517 1514 747 523 1255 586 895 555 1143 943 739 213 1036 1329 1869 683 835 1936 1121 100 11 3 1381 1612 518 363 1822 1927 404 1430 1040 1102 362 525 412 97 439 1432 1795 1504 1803 1439 469 891 858 1598 976 1919 1582 581 584 674 1340 580 1558 780 540 1940 900 916 642 683 418 1558 1473 403 1592 1672 1666 1351 1219 633 796 1486 671 137 895 385 1694 797 1497 1660 1002 186 873 1245 438 1873 387 1735 1110 1451 669 873 1462 1230 45 732 1946 1066 423 1243 608 1098 1054 1259 33 1197 91 1867 503 1217 908 204 833 1311 1533 247 65 661 1081 129 1906 1447 1988 1284 1393 60 310 296 1706 1900 441 517 623 1748 1096 1706 86 1661 285 473 1142 1032 965 24 1997 1217 1170 1933 779 230 1449 1844 430 1943 1595 716 290 826 1900 1774 847 483 481 146 455 631 1501 990 1819 811 340 766 1608 642 1471 1388 1265 1439 983 637 358 223 127 313 427 45 1616 14 702 968 302 843 888 405 688 1101 1906 1684 329 711 1867 102 914 209 1163 540 605 291 1786 722 551 1747 1833 745 284 297 1582 631 339 1461 1016 465 1114 37 1851 287 1440 1419 922 372 361 390 39 988 283 128 108 1761 1225 1477 549 1852 613 94 1424 500 376 1748 1601 1377 711 1089 581 1360 520 1555 1077 1029 832 1928 1175 1397 458 1445 1540 1886 1358 1358 809 1767 31 801 1520 90 202 698 1681 1703 1701 1728 128 231 1181 615 1190 16 601 1710 1444 1541 263 1984 1413 423 325 848 384 754 939 942 1454 484 1394 791 19 1943 1997 946 1790 352 357 309 930 9 504 618 1432 1572 279 1035 564 212 90 466 1892 925 255 1422 566 1861 847 1632 52 1701 1705 1593 1818 1929 1139 1263 389 141 781 187 1343 1810 387 1558 559 1127 1106 569 16 1430 524 1860 849 977 1121 1398 635 265 1281 993 616 509 423 636 1986 461 935 512 663 396 1416 1989 631 1534 542 33 1781 645 1088 1741 885 1210 1344 1841 1023 1021 546 660 1594 1144 1614 1699 1820 787 1439 276 517 945 1860 818 811 1426 1308 1048 1666 795 314 1504 299 3 1642 993 58 702 955 628 1952 1958 1281 1205 1599 1652 1397 1847 70 1510 1403 311 583 791 1261 871 1604 491 1712 732 1482 371 553 1812 978 607 829 1043 785 689 1381 535 1050 394 572 418 507 280 52 1274 222 1322 96 1377 1025 1832 592 1975 913 658 1332 1638 1770 629 1021 974 1245 1654 1739 1706 240 1389 145 572 428 1409 558 768 1219 478 1099 838 1994 1041 327 229 1379 1387 1994 1521 1162 839 95 1160 503 519 268 52 807 310 1310 1952 206 1164 1569 1593 1884 543 95 1447 782 1485 1635 1889 20 1629 749 1214 982 631 1112 565 390 598 1037 1295 61 1231 1267 939 515 117 709 721 1814 794 827 664 1111 1813 1153 1348 579 186 50 141 529 1071 1181 1732 1660 557 476 1583 891 57 414 1238 1075 341 245 475 1012 683 972 1214 1881 1096 1627 573 1622 925 1558 151 1046 1699 1208 1949 499 1880 1097 77 806 131 1371 412 1931 10 249 293 48 949 1428 695 498 1539 1071 1566 1641 1316 897 1110 1460 403 4 1313 1052 35 633 515 1118 1678 1881 588 1318 1571 1600 552 1127 1784 751 1838 1728 1468 1747 959 1208 807 359 1082 897 1309 1093 546 1756 1839 64 1673 390 819 1205 1870 1980 1085 764 182 1457 1912 1904 813 212 874 97 117 1079 785 328 351 698 1549 1151 620 247 105 660 1419 1004 1591 14 1790 1359 773 122 1120 380 1842 490 1789 1547 9 1480 1426 187 819 1746 217 915 405 1748 1199 1219 898 1109 1419 920 1270 843 202 393 1286 1372 79 576 1320 1896 1416 1927 643 1604 461 1922 1295 1191 1501 1554 195 482 639 704 1159 1126 1621 1573 1538 508 59 119 340 1229 34 642 478 110 1055 1239 74 1087 22 959 1209 1879 1547 248 1761 970 624 30 801 502 1024 1534 1402 1862 520 602 8 1153 879 1608 682 1034 1739 431 70 1454 1200 90 959 626 1333 1889 64 1788 1068 286 1580 411 1162 661 1382 1439 1483 1586 1916 927 1083 664 323 1296 80 2000 854 650 1906 934 1523 724 303 252 1213 1924 774 598 1582 251 1847 1179 435 1352 276 1407 757 811 617 450 1700 940 716 689 1549 1005 1281 1481 1636 577 959 880 1218 1122 1915 1078 1165 1574 1014 990 1531 925 806 140 689 338 393 599 954 1772 840 1786 1148 263 347 780 586 1929 1288 192 793 47 1581 726 1404 1929 1303 44 925 629 1970 1691 444 981 526 1251 1924 304 614 1458 735 1292 706 1257 1938 728 871 1188 1079 551 1916 275 287 1637 1877 1481 1166 932 4 925 1447 472 1307 1512 797 778 495 241 1183 684 1849 806 404 1408 1783 1445 1523 146 168 1604 140 311 946 1501 757 1373 883 888 744 1137 266 1458 41 451 67 1953 1284 925 692 1417 1180 483 1478 685 216 509 1362 732 1706 91 117 1366 1493 1336 1280 22 1527 571 702 1230 1881 133 1459 911 1816 807 143 118 280 846 1031 1643 759 1436 408 573 1933 123 169 1995 1854 310 1614 139 1509 1886 14 1415 1838 1851 1484 1351 307 1772 1011 1758 1593 1101 446 661 342 1008 935 1236 698 714 1697 1879 62 55 1708 1406 226 35 1361 1390 1520 1321 1287 1423 279 528 1225 1792 1527 1045 1428 1284 1702 486 1870 1007 484 1130 836 611 1415 828 165 1428 914 1315 842 1901 1178 1958 489 8 910 800 842 588 880 1426 1988 691 464 1826 1595 1867 417 1450 516 437 400 875 166 890 1793 1114 1945 289 498 1019 171 374 1325 165 1283 1384 423 1728 1483 336 1802 442 857 1202 266 1920 1718 441 1021 179 107 1230 978 1116 975 388 323 691 1815 1495 1029 1432 292 1952 492 1105 1785 564 632 691 466 1264 1773 971 1285 102 1693 1147 115 435 672 513 441 1259 645 1822 7 71 792 1775 527 257 582 1414 15 1304 1488 545 1974 1386 1716 1042 567 1272 1606 1065 1755 1549 467 612 1299 1552 565 242 426 925 658 1109 1744 1393 49 415 1980 1356 898 1654 1400 1039 1081 1102 1895 964 1386 1189 706 1289 368 479 1298 178 1706 866 637 227 153 447 1883 723 706 379 375 1881 1631 631 819 1463 1773 1758 544 539 405 576 577 1381 733 517 1464 70 149 95 1777 821 916 983 1234 296 1241 206 1464 1185 1112 815 1311 1967 538 509 777 1255 211 1982 1911 252 307 1501 1699 1800 1566 1799 1960 172 1796 401 1605 1428 742 1856 557 1760 75 76 807 1290 1588 520 321 839 892 1706 1125 1625 1418 807 653 786 698 1155 831 1629 1061 401 521 1812 1895 732 66 172 1045 1271 1596 428 350 419 1836 457 788 1864 1591 478 1646 1850 1121 702 659 890 1666 1725 1511 1563 1776 705 844 1347 1606 1351 1347 1259 951 1564 78 1593 1461 1764 1201 920 375 99 77 1691 685 559 811 1791 1322 1654 1059 509 483 1799 1722 1022 410 792 338 558 615 1027 1564 1598 759 1354 1112 1764 1449 264 1022 1113 1958 241 1182 335 247 1762 676 1955 1172 579 188 1949 1884 1445 996 1608 978 479 258 548 210 412 1541 1362 1537 701 441 1297 212 1573 488 1564 1352 310 1983 1441 700 2 602 946 334 1588 338 1829 991 74 1843 1701 985 1690 1216 279 320 156 562 1659 1215 468 312 775 17 205 1140 238 1173 1405 928 1245 58 511 757 1009 561 444 1540 1689 1771 440 1132 166 1898 688 1693 575 1395 820 1963 1885 968 1064 563 272 246 1501 457 1748 135 1110 1579 1486 1194 1237 414 1972 423 6 1720 1212 757 1293 1161 1397 829 1437 682 26 1616 82 1057 1193 1478 1974 1764 217 980 1270 370 1255 510 266 1000 343 1302 1785 358 445 486 655 1904 737 339 1110 1262 612 1545 1435 802 1982 1931 1976 1142 463 1630 360 1561 803 604 889 232 1968 122 1062 1335 1290 1428 1535 749 895 1284 1547 778 1561 1717 866 1286 280 470 614 18 912 1915 292
541