题目背景

译自 XXVIII Olimpiada Informatyczna - III etap Nawiasowania。

d2t2。

题目描述

有 $n$ 张卡片，每张上写了一个左括号或右括号。

按 $1\sim n$ 的顺序排列这些卡片，得到的括号序列是合法的。

给你一个长度为 $n$ 的排列 $p$。

按 $p$ 所示次序排列这些卡片，即新第 $i$ 张放原第 $p_i$ 张，得到的括号序列也是合法的。

构造符合要求的括号序列，按 $1\sim n$ 的顺序输出。

如果有多解，任意一种都行。无解输出 NIE。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数表示排列 $p$。

输出格式

如果有解，输出一行 $n$ 个字符，左括号或右括号。

如果无解，输出 NIE。

6
4 6 1 2 3 5

(()())

2
2 1

NIE

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

()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()

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

(()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()

见附件

NIE

见附件

见附件

提示

样例解释：

对于所有数据，$2\leq n\leq 1000000$。