input.txt

1000
9 310 1091 659 1748 1537 1913 380 700 1654 284 1782 1098 1653 1768 275 614 1161 211 461 707 394 1108 177 1424 760 1661 1752 1237 758 495 1589 1479 319 1260 151 1103 464 139 401 318 786 655 1104 1862 1932 1579 1906 994 133 1386 1387 649 340 386 1263 488 904 1023 63 123 1234 1926 1609 1517 1437 1877 645 1267 1653 1345 1725 633 1059 1474 1231 420 373 579 1657 98 756 750 315 1815 1563 619 573 769 1333 131 1231 1993 1469 500 1025 1673 893 558 1576 404 900 1902 1862 116 1448 542 1172 1879 172 1896 1609 224 1318 1579 1109 459 729 885 1970 395 1971 1075 1567 1305 1613 413 1284 1993 729 1588 665 1527 1354 246 5 892 26 81 118 1024 455 92 1801 1226 2 1671 56 353 1892 1911 222 1393 1064 1076 1054 61 2 1217 1324 878 238 1951 440 1304 1060 1117 308 1204 1376 1899 1925 838 965 1222 21 730 97 1434 372 1499 1654 1448 532 1511 514 523 1146 1662 493 1163 792 1565 1322 279 881 870 183 1214 501 193 1617 403 160 391 1151 1822 1117 1170 1676 77 897 1529 82 953 826 347 1958 211 1691 1932 266 73 97 265 733 449 1303 288 533 1681 829 1146 1801 1885 1306 1580 431 1734 817 376 1656 1054 1836 997 1977 443 372 1278 526 1058 874 742 588 297 811 307 78 736 225 1148 808 1715 570 1179 1180 1234 1595 1691 479 603 1749 778 89 700 607 1813 1260 829 868 1644 1096 387 352 1061 137 1133 551 1328 1316 311 1851 1496 319 125 1670 771 1642 1479 1884 632 1105 1223 923 1317 1030 1170 729 1574 1050 679 575 1987 582 13 799 1616 1282 1993 533 455 1778 556 952 991 875 201 84 1659 626 1800 394 357 1890 1439 1871 1370 1137 1365 940 819 504 1882 1466 35 135 813 685 1627 916 793 1313 1915 535 692 1509 242 1378 756 1308 1445 1515 625 1175 671 683 609 1225 1883 851 1366 331 1066 1442 552 65 475 911 1184 547 417 264 1890 698 1713 1986 759 632 1709 136 958 1173 142 43 262 657 235 202 302 291 641 1784 1613 1935 1652 861 531 1491 157 1839 1397 40 371 500 316 245 1453 1019 1840 543 338 484 1752 1810 1802 831 958 801 288 1916 1534 210 1835 495 1849 1507 656 28 373 1256 882 1117 839 687 1176 1908 1661 1742 1667 527 367 1479 668 1810 190 1860 1812 1168 1171 74 877 1996 244 1622 1710 1734 1068 1314 1142 1177 250 160 674 1559 1261 1351 171 1247 543 146 694 191 813 168 1431 837 887 1012 375 1416 1646 1125 928 1502 1413 195 1756 532 1496 1311 889 1926 1154 632 1775 440 179 1645 1131 38 42 1556 580 954 211 1070 1959 481 1053 1109 255 1892 403 1415 1504 660 1745 1937 1056 495 815 1951 450 1379 603 1851 1817 414 384 1958 165 668 1779 1816 172 1137 1776 95 440 201 791 1788 190 1934 374 560 127 27 1302 1066 903 370 1975 1488 1009 766 1525 905 445 84 1077 942 872 521 117 82 1136 1338 1520 490 309 814 1721 1260 1572 1206 1146 1361 1727 562 152 228 36 1547 905 304 1221 1170 1150 1418 1020 323 810 1039 1908 95 683 279 1485 1103 326 1868 894 1369 205 904 1467 667 1423 1233 1624 814 1160 1114 1451 654 1935 1700 1001 44 1469 215 701 400 503 1762 319 1126 1227 1808 966 1487 1062 785 192 1864 1037 804 284 1977 1822 1872 1795 1242 71 609 1548 1848 473 171 1534 1011 1181 86 1869 757 493 1551 544 1355 1754 2000 1107 129 1358 436 403 1839 1421 1400 734 1813 568 1013 1226 316 278 511 1317 1063 1034 38 1500 1403 70 1876 544 1482 1153 1619 1414 178 1534 1918 1433 492 527 1002 1244 1047 82 1147 521 278 1008 411 1095 876 1658 1631 721 1936 838 1191 139 1071 1813 1216 73 1462 1395 607 1807 303 877 945 437 1445 159 1946 1783 867 50 1068 185 441 1760 736 1179 205 40 273 906 339 1395 1580 1655 766 1736 1464 869 1084 1410 114 997 165 770 938 1992 1376 1552 386 1175 1601 267 1311 877 1951 203 1428 1391 732 1710 1509 1600 47 1513 768 1525 1294 444 1695 69 1574 242 174 1625 1219 1311 256 1181 1765 1627 1632 1392 61 1880 1674 46 1068 515 322 960 1078 665 1662 1476 123 377 527 1445 83 851 767 1886 1838 1890 844 1459 33 1283 1327 1156 530 1366 1365 593 857 1804 1722 1851 320 531 1084 380 490 684 1720 1893 1426 514 435 24 630 1093 1365 1851 145 1569 285 310 1046 410 572 209 1821 756 1882 420 1287 1878 1860 1984 367 951 497 153 1301 1640 1307 414 689 1934 1017 617 390 1504 1387 1541 1897 173 967 1483 403 1477 510 600 247 659 1896 275 1191 1153 1112 1193 562 1331 589 1195 573 1253 550 1493 1291 1380 1978 850 1357 388 1182 1745 962 1998 816 1123 1322 465 1000 453 7 769 100 1661 1678 394 1969 878 1447 1876 1633 1658 445 1813 392 1564 48 920 1446 1070 1327 1870 1344 1615 516 217 369 1095 185 1216 837 1861 278 732 1009 406 259 203 609 103 1525 1553 1595 687 1565 1531 616 935 1220 375 1873 648 508 1812 353 1981 1589 1692 141 1815 327 772 1777 39 1890 220 1048 1645 1980 190 365