from time import time
    
getallen = [704, 206, 291, 619, 554, 958, 737, 804, 260, 533, 137, 363, 770, 565, 912, 916, 715, 931, 846, 906, 772, 106, 843,
         50, 610, 448, 512, 466, 984, 660, 898, 49, 102, 467, 125, 579, 635, 72, 349, 891, 645, 707, 556, 330, 572, 368, 607,
         705, 937, 925, 214, 848, 833, 480, 234, 739, 47, 88, 141, 182, 541, 517, 321, 46, 313, 581, 942, 879, 372, 447, 259,
         853, 328, 683, 942, 63, 813, 511, 762, 871, 903, 78, 337, 272, 991, 870, 367, 128, 975, 418, 418, 875, 258, 678, 622,
         359, 453, 147, 620, 431, 543, 592, 44, 605, 792, 704, 763, 124, 63, 509, 825, 170, 655, 181, 487, 997, 328, 785, 466,
         964, 267, 878, 291, 666, 210, 417, 9, 749, 307, 726, 999, 849, 856, 812, 27, 958, 706, 585, 981, 252, 673, 963, 306,
         595, 109, 771, 52, 33, 366, 878, 378, 344, 981, 557, 275, 472, 373, 893, 803, 980, 521, 219, 349, 735, 256, 977, 154,
         735, 88, 490, 641, 973, 463, 550, 999, 10, 648, 527, 9, 613, 387, 341, 39, 756, 59, 130, 555, 761, 645, 392, 574, 509,
         827, 224, 962, 337, 268, 995, 795, 923, 445, 999, 477, 888, 474, 350, 876, 495, 823, 489, 239, 344, 763, 364, 697, 761,
         28, 952, 935, 448, 429, 147, 862, 557, 923, 594, 80, 250, 808, 7, 620, 136, 297, 610, 263, 425, 472, 731, 639, 475, 7,
         409, 444, 215, 23, 217, 379, 603, 437, 533, 60, 998, 708, 281, 254, 59, 542, 892, 811, 886, 485, 977, 482, 255, 483, 358,
         378, 359, 465, 811, 747, 162, 391, 454, 238, 397, 606, 851, 410, 624, 386, 968, 911, 521, 370, 140, 57, 732, 419, 632, 110,
         748, 968, 672, 827, 529, 229, 969, 17, 882, 468, 390, 795, 69, 405, 239, 2, 516, 80, 845, 140, 778, 663, 794, 721, 279, 5,
         790, 40, 122, 382, 319, 338, 517, 179, 472, 300, 354, 557, 583, 807, 205, 945, 207, 631, 936, 242, 755, 261, 799, 630, 606,
         500, 861, 453, 222, 339, 943, 468, 2, 246, 990, 912, 524, 144, 286, 115, 21, 367, 917, 442, 295, 85, 452, 562, 672, 684,
         3, 409, 796, 688, 863, 77, 667, 361, 956, 905, 404, 960, 340, 179, 315, 703, 197, 420, 698, 536, 677, 202, 891, 88, 225,
         86, 142, 757, 261, 495, 365, 699, 993, 384, 319, 561, 786, 854, 712, 203, 113, 623, 446, 140, 424, 42, 903, 933, 981, 868,
         14, 525, 187, 877, 258, 67, 263, 344, 142, 112, 342, 400, 497, 891, 324, 953, 319, 778, 610, 556, 645, 458, 636, 774, 12,
         944, 917, 571, 975, 217, 603, 393, 274, 471, 973, 343, 22, 598, 113, 807, 587, 691, 228, 710, 629, 628, 557, 907, 985, 684,
         904, 616, 716, 787, 700, 219, 145, 98, 508, 682, 776, 229, 399, 54, 960, 81, 48, 488, 240, 22, 621, 618, 823, 44, 831, 928,
         416, 669, 6, 92, 343, 54, 726, 296, 474, 72, 578, 377, 10, 485, 83, 870, 352, 516, 682, 317, 840, 919, 686, 137, 253, 825, 932,
         155, 7, 141, 383, 352, 907, 311, 449, 299, 320, 266, 786, 45, 551, 610, 609, 267, 449, 391, 349, 303, 320, 160, 349, 554, 970,
         324, 477, 550, 634, 765, 419, 184, 657, 270, 628, 48, 245, 236, 533, 709, 442, 924, 534, 218, 202, 499, 616, 200, 661, 708, 836,
         97, 174, 410, 942, 586, 489, 93, 808, 569, 955, 352, 912, 22, 150, 19, 629, 632, 127, 252, 898, 325, 162, 992, 323, 630, 749, 386,
         871, 73, 475, 247, 97, 225, 406, 459, 918, 807, 813, 11, 13, 594, 526, 627, 322, 91, 770, 158, 965, 91, 703, 831, 190, 77, 610, 885,
         113, 621, 750, 692, 146, 644, 217, 168, 669, 697, 126, 14, 883, 480, 548, 991, 483, 763, 775, 739, 860, 636, 201, 670, 623, 642,
         899, 551, 14, 993, 62, 653, 41, 309, 149, 905, 413, 910, 494, 148, 968, 550, 53, 118, 376, 780, 250, 812, 816, 943, 703, 308, 377,
         715, 685, 909, 543, 134, 333, 938, 10, 137, 388, 179, 288, 385, 165, 941, 476, 946, 562, 779, 642, 368, 39, 743, 369, 340, 747, 10,
         350, 650, 102, 640, 971, 200, 499, 604, 610, 207, 653, 320, 534, 84, 611, 392, 321, 33, 97, 601, 609, 429, 938, 870, 25, 262, 995,
         649, 152, 488, 619, 793, 530, 27, 985, 702, 843, 197, 289, 432, 558, 341, 187, 213, 513, 764, 848, 126, 55, 81, 803, 767, 976, 866,
         78, 391, 646, 161, 168, 520, 650, 933, 968, 795, 445, 111, 802, 431, 36, 652, 192, 500, 460, 830, 277, 807, 254, 701, 805, 235, 825,
         99, 960, 453, 625, 116, 10, 369, 574, 643, 103, 15, 669, 11, 191, 575, 439, 409, 881, 529, 406, 448, 139, 69, 699, 532, 836, 405, 491,
         947, 463, 31, 664, 580, 413, 162, 128, 565, 575, 94, 251, 261, 635, 814, 807, 779, 686, 361, 54, 685, 835, 24, 574, 883, 902, 921, 991,
         19, 16, 346, 834, 81, 47, 1000, 815, 325, 249, 667, 365, 453, 621, 184, 387, 582, 761, 768, 242, 593, 424, 36, 330, 953, 390, 71, 928,
         899, 62, 413, 633, 695, 218, 1, 7, 359, 236, 142, 84, 503, 124, 254, 380, 520, 195, 358, 781, 453, 225, 175, 430, 390, 164, 520, 607,
         280, 467, 436, 282, 887, 389, 173, 127, 488, 611, 773, 975, 721, 856, 807, 920, 429, 762, 837, 457, 799, 217, 105, 670, 705, 553, 174,
         356, 868, 95, 733, 269, 172, 57, 264, 472, 298, 488, 341, 517, 886, 39, 8, 347, 916, 175, 530, 306, 784, 936, 204, 885, 502, 463, 758,
         831, 303, 570, 278, 276, 26, 382, 535, 435, 704, 268, 809, 900, 969, 650, 536, 937, 68, 261, 106, 645, 822, 139, 726, 806, 4, 987, 975,
         559, 497, 468, 465, 382, 577, 95, 334, 510, 359, 214, 201, 436, 41, 755, 20, 708]


def maximum_1(lst):
    if len(lst) == 1:
        return lst[0]
    m = len(lst) // 2
    l_m = maximum_1(lst[:m])
    r_m = maximum_1(lst[m:])
    return max(l_m, r_m)


def maximum_2(lst):
    m = lst[1]
    for i in range(len(lst)):
        g = True
        for j in range(len(lst)):
            if lst[j] > lst[i]:
                g = False
        if g:
            m = lst[i]
    return m

# tijdsonderzoek