// permutacio.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <bits/stdc++.h>
using namespace std;
int main()
{
   /* string s = "3 2 4 7 8 9 10 6 11 13 14 12 15 5 16 17 1 20 19 18 22 21 23 24 25 26 30 29 28 27 31 35 36 37 34 38 39 33 40 32 41 42 44 45 47 49 48 46 43 50 51 54 58 59 60 62 66 68 67 69 71 72 74 75 77 76 79 78 73 70 81 83 85 84 86 87 89 90 92 93 91 94 96 95 98 99 101 102 100 103 105 104 97 106 107 109 110 112 111 113 108 88 114 115 82 116 80 65 117 119 118 64 121 122 123 120 124 125 126 63 61 127 57 128 129 56 131 130 133 134 132 135 137 136 140 142 141 143 148 150 152 153 155 154 156 157 158 151 162 161 160 159 165 166 168 167 169 164 170 163 171 149 172 147 174 175 176 178 179 177 173 180 182 183 184 185 186 187 181 188 146 145 190 189 191 193 194 196 197 199 200 198 201 202 195 204 208 209 207 210 211 212 213 216 215 214 217 218 219 222 223 221 225 226 229 228 230 231 227 233 234 235 236 238 240 241 242 243 246 245 247 244 239 249 248 252 254 255 253 256 251 259 258 265 266 264 263 268 269 271 272 270 274 275 273 278 279 277 281 282 286 288 289 287 285 284 283 290 291 292 280 293 276 267 294 299 300 301 302 298 297 296 303 295 304 305 306 262 309 308 310 307 311 261 260 257 312 250 237 313 314 232 224 315 319 320 321 322 323 324 325 327 328 330 331 329 332 333 326 334 339 340 338 337 341 342 343 345 344 336 349 348 350 347 346 335 352 351 354 353 356 355 357 358 359 318 317 360 316 220 206 361 362 205 364 363 366 367 369 368 370 365 203 372 371 192 144 374 375 373 376 377 379 378 380 139 381 138 55 383 382 53 384 52 385 386 387 389 390 392 391 388 393 394 395 398 399 401 402 403 400 405 406 407 408 404 397 409 410 396 414 415 416 417 419 420 418 413 412 411 421 424 425 426 427 428 423 429 430 422 433 434 432 437 438 439 440 441 442 445 446 447 448 449 450 444 443 451 453 452 454 456 457 458 460 459 462 463 468 469 472 473 475 478 480 479 482 481 477 476 474 471 470 467 466 483 486 488 487 485 490 491 492 493 494 489 497 496 500 501 502 503 499 504 505 498 495 506 508 509 511 510 512 513 507 516 520 522 523 526 527 525 524 528 529 530 521 531 532 533 534 535 519 538 539 537 536 541 546 547 545 544 549 550 551 553 554 555 556 557 552 558 561 562 565 566 567 564 563 568 560 569 571 570 559 548 543 542 574 576 578 579 580 581 582 577 583 584 585 586 587 588 589 591 593 594 592 596 595 590 575 597 602 604 603 605 606 607 608 609 610 611 601 612 613 615 616 617 618 614 621 622 626 627 629 633 634 636 637 635 632 638 631 639 640 630 642 641 648 647 649 650 646 645 644 651 652 653 655 656 658 657 659 654 660 661 643 663 664 665 662 666 667 628 669 668 625 672 671 673 676 675 678 677 679 674 680 683 684 686 687 688 690 689 691 692 685 682 695 697 698 702 701 703 704 706 710 711 712 709 713 715 716 717 719 720 718 721 714 708 723 724 722 707 725 727 726 729 731 734 735 737 736 740 739 743 744 747 748 751 752 753 750 749 746 754 755 756 757 758 759 745 742 761 762 763 760 741 738 733 764 765 766 732 769 768 767 770 771 775 774 776 773 777 780 779 781 782 778 784 785 787 786 790 789 791 788 792 793 794 783 772 795 730 728 796 705 797 798 800 801 802 803 806 807 809 810 812 813 811 808 805 804 814 815 818 819 821 822 820 823 824 817 825 826 827 828 816 799 831 832 833 830 829 834 835 836 837 838 839 841 840 842 700 843 699 846 848 847 849 845 853 855 857 856 858 854 859 852 860 861 862 863 865 866 867 864 869 870 871 872 873 868 874 875 876 877 851 850 844 879 878 882 884 885 883 881 886 880 887 888 696 889 890 891 694 892 693 681 893 670 894 624 623 895 620 899 900 902 904 906 907 909 908 905 911 912 914 915 916 913 917 910 919 921 923 924 925 922 926 920 918 903 901 930 931 932 934 933 929 928 936 935 937 940 942 943 941 944 939 945 938 927 946 947 950 949 948 898 897 952 951 896 953 956 955 960 959 958 961 962 957 963 964 954 619 965 966 968 969 967 600 970 971 599 972 974 975 976 973 977 978 979 981 983 982 986 988 989 990 991 987 992 993 995 996 994 997 998 985 999 1000 1002 1001 1004 1005 1006 1003 1007 984 1009 1010 1011 1012 1008 980 598 573 1013 572 1014 1016 1015 1017 1018 1019 540 1020 518 1021 1023 1022 1026 1027 1028 1029 1030 1031 1033 1032 1025 1034 1024 517 1035 515 1037 1036 514 1038 484 1039 465 464 1040 461 1042 1041 1046 1048 1047 1050 1053 1055 1056 1057 1054 1058 1059 1060 1061 1062 1052 1064 1066 1068 1070 1071 1073 1074 1072 1076 1077 1078 1075 1069 1079 1080 1067 1082 1085 1084 1086 1087 1083 1088 1081 1089 1090 1092 1094 1093 1096 1097 1098 1099 1100 1095 1102 1103 1104 1101 1107 1108 1110 1111 1112 1114 1113 1115 1118 1117 1116 1119 1120 1125 1126 1127 1128 1129 1132 1134 1137 1139 1140 1141 1138 1142 1143 1144 1145 1136 1135 1133 1131 1130 1124 1147 1148 1149 1150 1151 1153 1154 1156 1157 1158 1159 1161 1162 1160 1163 1168 1169 1170 1171 1172 1174 1176 1177 1178 1180 1179 1181 1175 1182 1173 1183 1167 1166 1186 1187 1185 1184 1188 1189 1165 1191 1192 1193 1190 1194 1164 1195 1196 1199 1200 1201 1202 1198 1203 1207 1208 1210 1211 1213 1214 1215 1216 1217 1218 1219 1212 1209 1206 1220 1205 1221 1204 1197 1155 1152 1146 1123 1222 1225 1226 1228 1227 1230 1231 1229 1224 1233 1234 1235 1237 1236 1232 1238 1239 1240 1241 1242 1223 1243 1122 1244 1121 1246 1249 1248 1250 1252 1251 1247 1245 1109 1253 1254 1255 1256 1257 1106 1105 1258 1259 1091 1260 1261 1262 1266 1267 1265 1264 1263 1065 1063 1268 1269 1271 1270 1051 1272 1273 1049 1045 1044 1043 1274 455 436 435 1275 1279 1278 1280 1281 1282 1277 1276 1283 1284 1285 1287 1288 1289 1286 1293 1292 1294 1295 1298 1297 1299 1302 1303 1304 1305 1306 1308 1307 1301 1310 1311 1315 1317 1322 1321 1320 1323 1319 1326 1328 1329 1330 1332 1334 1335 1336 1337 1340 1341 1339 1345 1344 1346 1347 1349 1348 1343 1350 1351 1352 1353 1342 1354 1338 1356 1355 1357 1333 1331 1359 1361 1360 1362 1363 1358 1365 1367 1368 1369 1370 1371 1366 1373 1374 1375 1372 1377 1376 1364 1379 1380 1378 1327 1325 1381 1382 1384 1387 1388 1386 1390 1391 1389 1385 1392 1394 1393 1395 1383 1324 1318 1316 1396 1398 1399 1400 1397 1314 1402 1401 1403 1313 1312 1405 1406 1404 1407 1408 1409 1410 1412 1413 1414 1411 1417 1416 1420 1421 1422 1423 1426 1428 1427 1425 1430 1432 1431 1433 1434 1429 1435 1436 1437 1424 1438 1439 1440 1442 1444 1445 1443 1446 1447 1441 1419 1418 1448 1449 1450 1453 1456 1455 1459 1461 1460 1462 1465 1467 1468 1469 1470 1471 1472 1473 1474 1476 1475 1466 1464 1479 1481 1483 1484 1485 1486 1489 1488 1493 1492 1497 1498 1499 1500 1501 1496 1502 1495 1494 1491 1490 1487 1504 1506 1507 1508 1509 1510 1505 1503 1482 1480 1511 1512 1513 1514 1515 1517 1516 1518 1478 1520 1521 1522 1524 1527 1528 1530 1532 1533 1535 1534 1531 1529 1536 1537 1538 1539 1526 1540 1542 1544 1546 1549 1548 1550 1551 1552 1553 1554 1555 1547 1556 1557 1561 1560 1562 1565 1566 1567 1571 1572 1573 1570 1574 1569 1575 1568 1564 1576 1577 1563 1578 1559 1579 1580 1582 1581 1558 1545 1543 1584 1585 1583 1586 1541 1587 1588 1525 1523 1589 1592 1595 1594 1593 1596 1598 1601 1600 1604 1603 1602 1605 1599 1597 1607 1608 1606 1611 1612 1614 1613 1610 1615 1616 1617 1618 1609 1620 1622 1621 1625 1624 1627 1626 1628 1623 1619 1629 1591 1590 1630 1632 1633 1635 1636 1634 1637 1638 1639 1643 1642 1641 1644 1646 1645 1640 1631 1649 1650 1653 1654 1652 1651 1648 1655 1656 1657 1647 1519 1658 1477 1463 1458 1457 1660 1662 1661 1663 1659 1664 1665 1666 1667 1454 1452 1668 1669 1451 1670 1415 1672 1673 1671 1675 1676 1681 1683 1682 1686 1688 1689 1687 1685 1690 1684 1691 1693 1696 1695 1698 1697 1694 1699 1692 1700 1680 1679 1701 1703 1706 1707 1708 1709 1710 1711 1705 1712 1713 1704 1714 1715 1702 1716 1717 1718 1720 1723 1726 1725 1727 1724 1728 1722 1721 1729 1719 1730 1731 1678 1732 1677 1674 1734 1735 1737 1736 1738 1739 1733 1309 1740 1742 1743 1741 1744 1300 1745 1746 1296 1291 1749 1748 1751 1752 1750 1753 1747 1754 1755 1290 1757 1760 1762 1764 1763 1765 1766 1769 1768 1767 1761 1770 1772 1773 1771 1774 1776 1777 1778 1779 1780 1781 1775 1783 1784 1785 1787 1788 1789 1791 1790 1792 1786 1782 1793 1795 1794 1796 1759 1799 1803 1804 1805 1808 1809 1810 1811 1807 1806 1812 1815 1816 1817 1818 1814 1813 1819 1802 1820 1821 1822 1801 1800 1823 1798 1824 1797 1826 1825 1832 1833 1834 1835 1836 1838 1837 1839 1840 1841 1843 1844 1842 1831 1830 1829 1845 1847 1848 1846 1849 1828 1850 1852 1853 1851 1854 1855 1856 1857 1858 1861 1860 1862 1864 1865 1866 1867 1868 1863 1869 1859 1827 1870 1872 1873 1871 1874 1758 1875 1876 1877 1756 1878 431 1879 1886 1887 1890 1891 1894 1895 1893 1892 1897 1896 1898 1889 1899 1888 1900 1885 1884 1901 1906 1905 1907 1904 1908 1909 1910 1912 1914 1915 1916 1913 1917 1918 1911 1903 1919 1902 1920 1921 1883 1922 1882 1881 1880 1923 1925 1926 1924 1928 1931 1930 1932 1934 1935 1937 1936 1933 1929 1927 1940 1945 1944 1943 1946 1947 1948 1942 1941 1949 1951 1950 1953 1952 1939 1954 1955 1938 1956 1957 1958 1959 1960 1962 1964 1963 1965 1966 1961 1968 1970 1971 1972 1969 1967 1973 1974 1978 1979 1977 1976 1984 1986 1987 1985 1988 1989 1990 1995 1997 1999 2000 2001 2002 2003 2004 1998 2005 1996 2006 2007 2009 2015 2017 2016 2019 2020 2021 2018 2014 2022 2023 2025 2024 2027 2030 2031 2032 2029 2033 2028 2026 2034 2035 2036 2038 2037 2039 2013 2040 2012 2011 2041 2043 2044 2042 2045 2046 2047 2010 2048 2049 2008 1994 2050 1993 2053 2054 2055 2052 2056 2057 2058 2051 2059 2060 1992 2061 1991 2062 2063 2064 1983 1982 2065 2066 2067 1981 2068 2071 2072 2073 2074 2070 2069 2077 2076 2080 2081 2083 2082 2085 2084 2079 2086 2089 2090 2088 2091 2093 2096 2099 2105 2104 2107 2106 2103 2111 2113 2112 2115 2114 2110 2116 2117 2118 2109 2108 2120 2122 2123 2121 2124 2125 2126 2119 2127 2102 2101 2128 2100 2098 2129 2134 2136 2139 2142 2141 2143 2145 2146 2144 2147 2148 2140 2149 2152 2155 2157 2156 2154 2153 2151 2160 2161 2162 2163 2164 2165 2159 2158 2168 2167 2169 2171 2170 2172 2166 2150 2174 2173 2138 2175 2137 2176 2135 2133 2132 2177 2131 2178 2180 2181 2184 2183 2185 2186 2187 2188 2189 2182 2190 2192 2193 2191 2179 2194 2195 2196 2197 2130 2199 2200 2198 2201 2097 2095 2202 2203 2094 2204 2205 2206 2207 2209 2210 2211 2208 2213 2212 2214 2215 2217 2218 2219 2220 2216 2222 2221 2223 2224 2092 2225 2228 2227 2229 2226 2231 2232 2234 2236 2237 2239 2238 2235 2241 2240 2233 2230 2243 2244 2245 2246 2247 2242 2248 2087 2249 2250 2252 2251 2253 2254 2078 2075 2255 2256 2258 2257 2259 2260 2261 2262 2263 2264 2265 2266 1980 2267 2268 2269 1975 2270 2272 2275 2274 2273 2276 2277 2278 2271 2279 2281 2282 2284 2285 2283 2286 2288 2290 2294 2295 2293 2296 2298 2299 2300 2297 2292 2301 2291 2302 2289 2303 2305 2307 2306 2304 2310 2311 2312 2315 2317 2316 2314 2318 2319 2320 2321 2313 2309 2322 2326 2327 2332 2333 2334 2331 2335 2330 2336 2337 2329 2328 2338 2340 2341 2339 2342 2343 2325 2345 2347 2349 2350 2351 2348 2352 2346 2356 2358 2362 2365 2364 2366 2367 2370 2371 2372 2369 2373 2374 2376 2377 2383 2384 2385 2382 2386 2387 2388 2389 2381 2390 2380 2391 2379 2392 2394 2395 2393 2396 2397 2378 2398 2399 2401 2402 2400 2403 2404 2375 2405 2368 2407 2408 2406 2363 2409 2411 2417 2418 2419 2416 2420 2422 2423 2425 2426 2427 2428 2430 2429 2431 2424 2421 2415 2432 2433 2434 2435 2414 2436 2438 2440 2441 2442 2446 2447 2449 2450 2451 2452 2453 2448 2445 2454 2455 2457 2458 2456 2459 2461 2463 2464 2462 2466 2465 2467 2468 2460 2444 2470 2472 2471 2474 2473 2469 2443 2439 2475 2437 2413 2476 2477 2478 2479 2480 2481 2483 2484 2482 2485 2412 2490 2491 2493 2494 2499 2500 2502 2501 2498 2497 2503 2505 2506 2507 2509 2510 2511 2508 2504 2514 2515 2518 2519 2522 2521 2520 2517 2516 2526 2530 2531 2529 2533 2532 2535 2534 2536 2528 2537 2539 2540 2542 2543 2544 2541 2545 2547 2548 2550 2553 2555 2556 2554 2557 2558 2561 2562 2560 2563 2559 2552 2565 2564 2567 2566 2568 2551 2570 2569 2549 2546 2571 2574 2577 2576 2575 2580 2581 2582 2584 2585 2583 2579 2586 2588 2587 2589 2590 2591 2593 2594 2592 2598 2600 2599 2597 2596 2601 2603 2604 2606 2605 2602 2608 2611 2610 2612 2613 2609 2614 2616 2615 2617 2607 2595 2618 2620 2622 2623 2624 2625 2626 2621 2628 2629 2627 2619 2630 2578 2631 2573 2572 2633 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2647 2648 2646 2649 2645 2650 2634 2653 2654 2652 2651 2632 2655 2538 2656 2527 2525 2658 2657 2659 2524 2523 2660 2513 2661 2512 2663 2662 2664 2665 2670 2669 2671 2668 2667 2672 2674 2675 2673 2677 2678 2679 2680 2681 2676 2682 2685 2693 2695 2694 2696 2700 2699 2701 2698 2703 2704 2705 2702 2706 2707 2708 2709 2711 2712 2713 2710 2714 2723 2724 2727 2728 2726 2730 2731 2732 2733 2729 2725 2735 2734 2736 2722 2721 2720 2738 2739 2737 2741 2746 2750 2753 2752 2751 2755 2756 2754 2749 2757 2748 2758 2747 2759 2760 2761 2762 2763 2764 2765 2767 2768 2766 2769 2745 2744 2770 2771 2772 2773 2743 2774 2742 2775 2776 2777 2778 2740 2779 2719 2780 2781 2782 2783 2718 2785 2788 2787 2789 2786 2784 2790 2717 2716 2715 2792 2794 2795 2796 2793 2791 2797 2798 2801 2800 2803 2804 2802 2805 2806 2809 2811 2810 2814 2815 2813 2812 2816 2817 2818 2808 2820 2821 2819 2822 2823 2825 2824 2826 2807 2827 2828 2830 2829 2831 2832 2799 2834 2833 2835 2697 2836 2837 2692 2838 2691 2840 2839 2690 2841 2842 2689 2688 2843 2687 2686 2844 2684 2845 2683 2846 2666 2848 2849 2847 2851 2850 2496 2852 2495 2853 2854 2855 2856 2857 2492 2858 2860 2861 2859 2862 2863 2489 2865 2869 2871 2872 2875 2874 2876 2873 2870 2868 2867 2877 2866 2878 2879 2880 2864 2488 2885 2886 2884 2887 2883 2882 2888 2889 2890 2891 2892 2893 2895 2896 2898 2899 2900 2897 2901 2903 2904 2902 2906 2907 2908 2909 2910 2911 2905 2894 2912 2913 2915 2916 2918 2919 2922 2923 2925 2926 2927 2928 2930 2931 2932 2933 2934 2935 2937 2936 2938 2929 2924 2939 2940 2921 2920 2943 2942 2946 2948 2947 2945 2951 2950 2954 2957 2956 2955 2958 2959 2953 2952 2949 2944 2961 2962 2960 2941 2965 2966 2964 2963 2917 2967 2969 2970 2971 2968 2914 2881 2975 2974 2976 2977 2978 2973 2972 2979 2487 2982 2983 2981 2980 2984 2986 2988 2989 2987 2990 2991 2992 2985 2993 2996 2995 3000 2999 2998 2997 2994 3001 3003 3004 3005 3006 3002 2486 2410 3007 3008 3010 3011 3014 3013 3016 3018 3020 3022 3023 3025 3026 3027 3030 3029 3031 3028 3024 3021 3019 3032 3033 3035 3034 3038 3037 3036 3039 3041 3040 3043 3042 3044 3047 3046 3045 3048 3051 3053 3054 3055 3052 3056 3050 3049 3057 3058 3059 3060 3061 3017 3062 3063 3015 3065 3066 3064 3067 3069 3068 3012 3070 3071 3072 3009 3073 3074 2361 3077 3078 3079 3076 3081 3085 3084 3086 3083 3088 3090 3089 3091 3092 3094 3095 3096 3093 3097 3087 3098 3100 3099 3101 3102 3104 3105 3103 3082 3080 3106 3108 3109 3111 3110 3113 3112 3115 3117 3118 3120 3121 3123 3124 3128 3131 3133 3135 3134 3138 3137 3139 3140 3136 3141 3143 3144 3145 3147 3148 3149 3150 3151 3155 3154 3153 3152 3158 3157 3162 3163 3164 3166 3169 3173 3175 3176 3174 3178 3177 3172 3171 3170 3181 3182 3180 3183 3184 3179 3186 3185 3187 3168 3188 3189 3190 3191 3167 3165 3192 3194 3195 3193 3197 3196 3198 3161 3201 3200 3204 3205 3206 3207 3203 3208 3209 3202 3212 3211 3213 3215 3218 3217 3219 3216 3214 3210 3220 3199 3221 3222 3223 3224 3227 3226 3228 3230 3231 3234 3233 3232 3229 3225 3236 3235 3237 3238 3240 3239 3241 3242 3243 3160 3245 3246 3247 3249 3250 3248 3244 3251 3159 3252 3253 3156 3256 3257 3258 3260 3261 3262 3263 3266 3265 3264 3259 3267 3268 3255 3269 3272 3274 3275 3276 3277 3281 3283 3285 3284 3282 3286 3287 3288 3291 3292 3293 3294 3295 3297 3298 3296 3290 3299 3300 3301 3289 3303 3304 3305 3302 3280 3279 3306 3278 3273 3308 3309 3312 3313 3311 3310 3307 3314 3315 3271 3317 3316 3318 3270 3319 3321 3320 3254 3322 3323 3325 3327 3328 3329 3326 3332 3331 3330 3324 3146 3142 3333 3132 3334 3130 3336 3335 3337 3129 3127 3338 3126 3125 3122 3339 3119 3116 3114 3107 3340 3341 3342 3343 3075 3344 3346 3347 3348 3345 3349 3350 3351 3355 3358 3357 3362 3363 3364 3365 3361 3360 3368 3369 3370 3371 3373 3374 3372 3375 3378 3379 3377 3381 3380 3376 3382 3383 3384 3385 3386 3387 3388 3391 3392 3390 3393 3394 3395 3389 3397 3398 3399 3402 3406 3408 3410 3411 3412 3418 3417 3419 3421 3422 3423 3424 3425 3420 3426 3427 3416 3415 3429 3430 3428 3431 3433 3437 3438 3440 3439 3441 3442 3436 3435 3443 3444 3445 3447 3446 3434 3448 3449 3451 3453 3452 3454 3450 3456 3457 3458 3460 3459 3461 3463 3464 3465 3462 3455 3470 3469 3468 3467 3472 3474 3476 3475 3478 3477 3479 3481 3480 3482 3473 3485 3486 3484 3483 3487 3471 3466 3488 3432 3489 3491 3490 3493 3494 3496 3497 3495 3492 3498 3499 3414 3500 3501 3413 3409 3502 3505 3504 3506 3503 3507 3508 3509 3510 3512 3511 3407 3513 3514 3405 3515 3516 3517 3518 3519 3404 3403 3521 3523 3524 3525 3522 3520 3527 3528 3533 3532 3534 3536 3537 3539 3540 3541 3538 3535 3531 3543 3544 3545 3547 3546 3548 3549 3542 3550 3551 3553 3554 3557 3560 3561 3559 3562 3563 3558 3564 3556 3565 3555 3566 3567 3568 3552 3569 3570 3571 3573 3575 3576 3579 3580 3583 3582 3585 3584 3581 3588 3589 3587 3590 3591 3592 3586 3594 3597 3598 3596 3599 3600 3601 3602 3603 3604 3595 3593 3606 3607 3608 3605 3610 3611 3613 3614 3612 3615 3616 3617 3618 3619 3620 3622 3623 3621 3626 3628 3627 3625 3624 3629 3630 3609 3631 3632 3633 3634 3635 3578 3577 3636 3638 3643 3644 3645 3646 3647 3648 3649 3652 3651 3650 3654 3655 3656 3659 3660 3658 3657 3661 3662 3664 3665 3666 3667 3663 3668 3653 3671 3673 3672 3675 3676 3677 3678 3679 3680 3681 3674 3682 3684 3685 3687 3688 3689 3686 3693 3694 3695 3697 3699 3698 3700 3701 3702 3703 3704 3705 3696 3706 3708 3712 3711 3715 3716 3717 3718 3721 3720 3719 3722 3727 3726 3725 3729 3730 3732 3733 3734 3731 3728 3724 3723 3738 3740 3739 3745 3744 3746 3743 3742 3747 3748 3741 3751 3752 3753 3755 3754 3756 3750 3757 3760 3759 3761 3758 3763 3764 3762 3767 3769 3770 3771 3768 3773 3772 3774 3766 3779 3780 3782 3783 3784 3785 3781 3786 3778 3777 3787 3789 3790 3788 3776 3793 3792 3791 3775 3765 3794 3795 3796 3798 3800 3799 3797 3801 3802 3803 3749 3737 3804 3805 3736 3735 3714 3713 3806 3710 3709 3807 3707 3692 3691 3808 3809 3690 3810 3811 3812 3683 3815 3816 3818 3821 3822 3824 3825 3823 3826 3820 3827 3828 3829 3830 3831 3819 3832 3833 3817 3834 3835 3814 3836 3837 3838 3839 3813 3841 3840 3842 3843 3670 3669 3844 3642 3845 3846 3847 3848 3641 3640 3850 3851 3852 3849 3853 3854 3855 3639 3637 3856 3857 3858 3574 3859 3860 3862 3863 3861 3572 3864 3865 3868 3867 3869 3872 3874 3875 3878 3877 3876 3873 3871 3879 3880 3881 3870 3885 3886 3884 3889 3888 3890 3891 3893 3894 3895 3892 3896 3887 3898 3899 3900 3902 3903 3901 3906 3908 3909 3910 3907 3905 3911 3912 3913 3914 3904 3915 3916 3897 3917 3918 3883 3920 3919 3882 3921 3923 3922 3924 3866 3530 3529 3925 3926 3927 3526 3928 3401 3400 3929 3396 3932 3933 3934 3935 3936 3939 3938 3940 3941 3937 3942 3931 3947 3946 3950 3951 3949 3948 3952 3945 3944 3953 3943 3955 3958 3959 3962 3963 3961 3964 3967 3969 3970 3973 3972 3971 3975 3977 3978 3976 3979 3974 3980 3982 3981 3983 3985 3984 3986 3987 3989 3990 3991 3992 3993 3988 3995 3994 3996 3968 3966 3997 3965 3998 3999 4001 4000 3960 4003 4004 4002 4005 3957 4006 4007 3956 4009 4011 4012 4010 4014 4013 4015 4017 4018 4019 4020 4016 4022 4025 4026 4027 4028 4024 4023 4029 4021 4031 4033 4032 4036 4037 4035 4038 4034 4039 4030 4041 4042 4043 4045 4044 4046 4047 4040 4008 3954 3930 3367 4048 4051 4050 4049 4053 4052 4055 4057 4059 4060 4061 4058 4062 4064 4063 4056 4065 4054 4066 4068 4067 4069 4072 4071 4074 4075 4073 4077 4079 4080 4078 4083 4084 4085 4086 4087 4082 4081 4076 4088 4090 4091 4089 4070 4092 4093 4094 3366 4096 4097 4101 4102 4108 4107 4109 4110 4111 4106 4105 4104 4113 4115 4116 4118 4117 4120 4122 4121 4124 4125 4127 4126 4129 4128 4130 4135 4136 4137 4134 4139 4140 4141 4138 4133 4142 4144 4145 4143 4132 4146 4131 4123 4119 4149 4151 4152 4150 4148 4153 4154 4147 4155 4156 4157 4158 4114 4159 4112 4160 4103 4161 4162 4164 4165 4168 4169 4167 4170 4172 4173 4174 4175 4171 4166 4163 4177 4179 4180 4181 4182 4183 4184 4178 4186 4185 4187 4188 4176 4100 4189 4190 4191 4099 4195 4196 4198 4199 4197 4200 4194 4201 4193 4202 4192 4203 4098 4204 4095 3359 4205 4206 4210 4211 4213 4214 4215 4217 4218 4216 4222 4223 4224 4225 4221 4220 4226 4228 4229 4230 4227 4231 4219 4232 4233 4234 4235 4212 4236 4237 4239 4240 4241 4238 4209 4242 4244 4243 4246 4248 4247 4249 4245 4250 4208 4253 4254 4252 4251 4255 4207 4257 4258 4260 4261 4263 4262 4264 4265 4259 4266 4256 3356 3354 4267 4268 4269 4270 4272 4271 4274 4276 4275 4277 4278 4280 4279 4283 4288 4290 4291 4289 4292 4293 4294 4296 4295 4287 4286 4297 4298 4299 4300 4285 4284 4301 4302 4303 4304 4305 4307 4308 4309 4310 4313 4312 4314 4311 4315 4306 4282 4281 4316 4317 4320 4319 4321 4322 4323 4324 4318 4273 4325 4329 4331 4334 4335 4336 4337 4333 4332 4330 4339 4338 4340 4341 4342 4343 4328 4327 4344 4345 4326 4346 4347 4348 3353 4349 4350 4353 4354 4355 4356 4357 4359 4361 4362 4360 4363 4364 4366 4365 4358 4367 4368 4369 4370 4371 4373 4372 4352 4375 4374 4376 4351 4377 3352 4378 4379 4380 4381 4383 4384 4382 2360 4385 4386 4387 2359 2357 2355 4388 4390 4389 2354 4391 2353 4392 4394 4393 4395 4396 4397 4398 2344 4399 2324 4402 4403 4404 4401 4400 2323 4406 4407 4408 4412 4413 4411 4414 4415 4410 4409 4418 4419 4417 4420 4421 4422 4416 4423 4424 4427 4429 4430 4431 4432 4428 4434 4433 4435 4426 4437 4439 4442 4443 4444 4441 4445 4446 4447 4448 4440 4438 4449 4436 4425 4451 4453 4454 4452 4455 4450 4456 4405 4457 4459 4461 4460 4466 4465 4468 4470 4469 4474 4473 4472 4471 4467 4476 4477 4478 4479 4475 4464 4463 4483 4484 4485 4482 4481 4486 4480 4488 4490 4489 4487 4493 4492 4494 4496 4498 4500 4499 4497 4502 4501 4495 4503 4504 4505 4506 4507 4508 4509 4491 4462 4510 4511 4512 4514 4515 4516 4517 4513 4520 4521 4519 4522 4518 4524 4526 4525 4523 4527 4528 4458 2308 4530 4529 4532 4535 4536 4537 4538 4534 4540 4539 4533 4541 4544 4545 4546 4543 4548 4549 4547 4550 4542 4531 4552 4555 4556 4557 4559 4560 4561 4558 4562 4563 4564 4565 4554 4553 4551 2287 4567 4568 4569 4570 4572 4574 4573 4571 4575 4576 4566 4577 4578 4580 4579 2280 4581 4583 4582 4586 4585 4587 4584 4590 4592 4593 4591 4594 4595 4589 4596 4588 4598 4599 4600 4597 4601 4603 4604 4602 4605 4606 4608 4607 4609 4611 4610 4612 4613 4614 4616 4617 4615 4618 4619 4620 4621 4622 4623 4627 4626 4625 4630 4631 4632 4633 4629 4634 4637 4636 4638 4635 4639 4640 4628 4641 4624 4643 4642 4644 4646 4645 4650 4652 4651 4649 4648 4654 4659 4661 4660 4658 4665 4666 4667 4668 4670 4671 4673 4672 4675 4674 4677 4676 4678 4679 4680 4684 4683 4685 4686 4687 4682 4689 4690 4688 4691 4692 4694 4693 4696 4697 4698 4695 4701 4702 4700 4699 4703 4704 4706 4705 4707 4709 4710 4711 4708 4713 4712 4714 4715 4717 4718 4720 4721 4722 4723 4719 4725 4724 4726 4716 4727 4728 4730 4731 4733 4732 4735 4736 4737 4739 4740 4743 4745 4746 4747 4744 4749 4751 4753 4754 4756 4755 4757 4758 4760 4761 4759 4762 4752 4768 4767 4766 4765 4764 4769 4770 4773 4774 4772 4776 4777 4775 4779 4778 4771 4763 4781 4782 4783 4780 4784 4750 4748 4742 4785 4741 4786 4787 4738 4788 4789 4790 4792 4791 4793 4795 4794 4734 4729 4796 4681 4797 4798 4669 4799 4664 4801 4800 4802 4803 4805 4806 4809 4810 4812 4813 4815 4816 4814 4811 4808 4820 4819 4821 4818 4817 4807 4822 4823 4826 4829 4828 4831 4832 4834 4833 4836 4837 4838 4840 4843 4847 4848 4849 4846 4845 4844 4842 4851 4850 4852 4854 4855 4853 4841 4857 4858 4856 4860 4859 4839 4861 4863 4862 4835 4865 4864 4866 4867 4869 4868 4830 4827 4825 4870 4872 4875 4876 4877 4878 4879 4880 4874 4881 4882 4883 4885 4886 4887 4888 4889 4890 4884 4891 4873 4893 4894 4895 4892 4871 4896 4824 4804 4897 4900 4901 4902 4899 4903 4906 4908 4909 4907 4910 4911 4905 4904 4912 4898 4913 4914 4915 4916 4917 4918 4919 4920 4663 4921 4924 4926 4929 4928 4930 4927 4931 4932 4935 4934 4933 4936 4925 4937 4938 4941 4942 4943 4940 4939 4944 4923 4922 4662 4945 4657 4946 4950 4949 4951 4948 4952 4947 4954 4953 4955 4656 4655 4956 4957 4958 4960 4962 4964 4966 4967 4968 4969 4970 4971 4973 4974 4972 4975 4976 4979 4978 4981 4982 4980 4977 4984 4985 4988 4989 4990 4987 4991 4986 4983 4994 4993 4996 4995 4992 4965 4963 4997 4998 5001 5003 5002 5000 5004 4999 5006 5010 5013 5016 5017 5019 5018 5015 5020 5014 5021 5023 5027 5028 5026 5029 5025 5030 5032 5031 5036 5037 5035 5034 5038 5033 5039 5040 5042 5046 5047 5050 5049 5051 5054 5053 5056 5057 5058 5055 5059 5060 5061 5062 5063 5064 5065 5066 5052 5069 5070 5071 5073 5072 5068 5074 5075 5076 5067 5048 5045 5044 5077 5079 5078 5080 5082 5084 5085 5087 5090 5092 5093 5094 5095 5096 5097 5098 5091 5089 5088 5086 5083 5099 5081 5100 5043 5041 5101 5102 5103 5104 5024 5105 5108 5107 5109 5106 5110 5022 5012 5111 5112 5118 5120 5121 5119 5122 5123 5124 5127 5128 5126 5125 5117 5129 5132 5131 5130 5116 5115 5134 5135 5136 5137 5133 5138 5139 5143 5144 5142 5149 5150 5151 5152 5148 5153 5154 5155 5147 5156 5159 5160 5161 5158 5163 5165 5164 5166 5167 5162 5157 5168 5169 5170 5171 5172 5146 5145 5141 5173 5174 5175 5177 5178 5176 5179 5140 5180 5114 5184 5185 5187 5188 5186 5189 5190 5191 5192 5183 5182 5193 5194 5195 5196 5198 5197 5200 5201 5202 5199 5203 5181 5113 5204 5011 5206 5207 5208 5209 5210 5211 5214 5215 5213 5216 5219 5220 5221 5222 5223 5218 5224 5217 5225 5226 5227 5212 5228 5205 5229 5231 5230 5232 5009 5237 5236 5238 5235 5240 5242 5241 5243 5244 5239 5246 5250 5249 5248 5252 5251 5253 5255 5256 5258 5257 5259 5254 5260 5262 5263 5266 5265 5264 5267 5261 5268 5269 5247 5271 5272 5274 5275 5277 5278 5279 5280 5283 5284 5285 5286 5282 5289 5288 5287 5290 5291 5293 5292 5296 5297 5295 5298 5299 5294 5300 5301 5302 5303 5306 5307 5308 5305 5309 5304 5312 5313 5314 5311 5315 5310 5316 5281 5317 5276 5318 5273 5270 5321 5323 5322 5325 5326 5328 5330 5332 5334 5333 5335 5336 5337 5339 5341 5340 5342 5347 5346 5345 5344 5348 5349 5352 5351 5353 5354 5350 5355 5356 5343 5338 5331 5359 5358 5360 5362 5363 5364 5366 5365 5361 5357 5367 5368 5369 5370 5371 5372 5329 5373 5374 5375 5376 5327 5377 5378 5379 5380 5381 5382 5383 5387 5386 5388 5389 5385 5390 5391 5384 5324 5320 5392 5393 5319 5245 5396 5402 5403 5401 5404 5400 5399 5398 5405 5397 5408 5409 5415 5416 5418 5417 5419 5420 5414 5422 5424 5426 5430 5429 5432 5434 5435 5438 5439 5440 5441 5446 5445 5444 5448 5447 5443 5449 5450 5442 5451 5452 5437 5454 5455 5457 5458 5459 5460 5462 5463 5464 5461 5465 5466 5467 5456 5468 5453 5470 5469 5471 5472 5436 5433 5431 5473 5479 5481 5482 5483 5480 5487 5488 5486 5489 5485 5490 5491 5484 5492 5497 5499 5500 5501 5498 5502 5496 5495 5494 5504 5506 5507 5509 5508 5510 5511 5518 5521 5520 5519 5523 5522 5524 5517 5525 5516 5526 5528 5529 5527 5515 5531 5532 5534 5533 5535 5530 5536 5537 5538 5540 5539 5541 5514 5543 5545 5546 5547 5548 5549 5544 5550 5552 5551 5555 5556 5554 5557 5553 5542 5513 5559 5558 5560 5561 5512 5563 5564 5562 5565 5505 5567 5568 5569 5571 5572 5575 5574 5576 5577 5578 5573 5570 5566 5579 5503 5493 5478 5580 5581 5584 5585 5583 5587 5589 5590 5588 5586 5591 5593 5594 5595 5596 5597 5598 5600 5599 5592 5602 5601 5582 5603 5604 5605 5477 5606 5611 5610 5609 5613 5614 5615 5619 5621 5620 5622 5618 5617 5626 5625 5627 5624 5629 5628 5630 5631 5632 5634 5637 5636 5640 5641 5642 5643 5644 5645 5639 5646 5647 5652 5654 5655 5656 5653 5659 5661 5663 5662 5660 5664 5666 5665 5667 5668 5658 5669 5657 5670 5672 5673 5674 5671 5651 5675 5676 5650 5677 5681 5682 5683 5685 5686 5687 5688 5692 5693 5697 5698 5699 5700 5696 5695 5701 5702 5703 5705 5706 5707 5709 5708 5711 5713 5714 5717 5716 5715 5718 5712 5710 5719 5704 5694 5721 5722 5724 5725 5726 5723 5727 5729 5731 5730 5732 5733 5728 5720 5691 5735 5734 5736 5739 5740 5741 5745 5744 5748 5747 5749 5750 5746 5743 5742 5751 5738 5737 5752 5690 5755 5756 5754 5758 5757 5753 5689 5761 5762 5763 5764 5766 5767 5765 5760 5759 5770 5772 5773 5774 5771 5775 5769 5776 5777 5778 5783 5782 5781 5785 5784 5780 5787 5786 5779 5788 5789 5791 5792 5793 5794 5795 5800 5799 5798 5802 5803 5804 5805 5807 5809 5810 5811 5812 5813 5808 5806 5814 5815 5816 5817 5801 5797 5818 5819 5820 5821 5796 5790 5822 5768 5823 5684 5824 5825 5680 5679 5828 5829 5830 5831 5833 5834 5835 5836 5832 5838 5837 5840 5839 5827 5843 5845 5846 5844 5842 5847 5841 5848 5850 5851 5853 5855 5857 5859 5858 5861 5860 5856 5862 5854 5852 5864 5863 5849 5866 5867 5868 5865 5869 5870 5826 5678 5872 5873 5871 5874 5875 5876 5649 5877 5881 5882 5883 5880 5879 5886 5887 5885 5888 5889 5890 5884 5891 5892 5894 5895 5896 5898 5897 5893 5878 5899 5648 5900 5901 5902 5903 5638 5904 5906 5907 5905 5908 5909 5635 5633 5910 5911 5623 5616 5912 5914 5913 5916 5917 5919 5921 5922 5923 5925 5928 5929 5930 5931 5932 5934 5933 5927 5935 5936 5939 5940 5941 5942 5943 5944 5945 5947 5946 5948 5951 5950 5954 5955 5958 5959 5957 5963 5964 5962 5965 5966 5967 5968 5961 5969 5970 5971 5974 5975 5976 5977 5978 5981 5982 5985 5986 5984 5983 5980 5979 5987 5988 5989 5991 5994 5995 5993 5996 5997 5998 5999 5992 5990 6000 5973 5972 5960 5956 5953 5952 5949 5938 5937 5926 5924 5920 5918 5915 5612 5608 5607 5476 5475 5474 5428 5427 5425 5423 5421 5413 5412 5411 5410 5407 5406 5395 5394 5234 5233 5008 5007 5005 4961 4959 4653 4647";
    stringstream ss(s);*/
    int n=6000;
    cin >> n; 
    vector<int> X(n, 0);
    //int cv = 0;
    //string sr = "";
    //while (getline(ss, sr, ' ')) {

    //    // store token string in the vector
    //    X[cv]=stoi(sr);
    //}
   
    for (size_t i = 0; i < n; i++)
    {
        cin >> X[i];
    }
    vector<int> Y;
    int db = n - 2;
    Y.push_back(X[n - 1]);
    while (db>0&&(X[db]<=X[db-1]))
    {
        Y.push_back(X[db]);
        db--;
    }
    int ut = X[db - 1];
    Y.push_back(X[db]);
    Y.push_back(X[db-1]);
    sort(Y.begin(),Y.end());
    int maxy = Y.capacity()-1;
    while (maxy>0&&Y[maxy-1]>ut)
    {
        maxy--;
    }
    
    X[db - 1] = Y[maxy];
  /*  for (int i = maxy-1; i >=0; i--)
    {
        X[db] = Y[i];
        db++;
    }*/
   /* for (int i = Y.capacity()-1; i > maxy; i--)
    {
        X[db] = Y[i];
        db++;
    }*/
    for (auto a : X)
    {
        cout << a<<" ";
    }
    cout << endl;
   
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file