P18666 [HackerEarth] You are given a permutation of integers from 1 to N (very unusual :D). The only thing you should do is to process M queries. Each query has 2 parameters: number X from 1 to N and lowerca
提高
题目描述

You are given a permutation of integers from 1 to N (very unusual :D). The only thing you should do is to process M queries. Each query has 2 parameters: number X from 1 to N and lowercase latin letter Y (either 'l' or 'r'). You do the following:
Calculate distances from the position of the number X to the left end and to the right end of the permutation. Let's call minimum of them accessibleness.
Erase number X from it's current position. If parameter Y is 'l' then insert X the very beginning of the permutation. Otherwise insert X after the last element of the permutation.

Please find sum of accessibleness over all queries.

Input
The first line contains two space-separated integers: N and M. The second line contains N space-separated integers: the initial permutation. After this M lines follow containing 2 space-separated parameters each in the way it's described in the statement above.

Output
Output one number - answer for the question.

Constraints
0 < N, M ≤ 500 000
0 < N, M ≤ 2 000 in 35 % of the test data.
0 < N, M ≤ 70 000 in 70 % of the test data.

SAMPLE INPUT
4 3
3 1 4 2
3 r
2 r
1 l

SAMPLE OUTPUT
1

Explanation

Permutation before the 1st query: 3 1 4 2. 3 has accessibleness 0.
Permutation before the 2nd query: 1 4 2 3. 2 has accessibleness 1.
Permutation before the 3rd query: 1 4 3 2. 1 has accessibleness 0.
So the sum over all queries is 1.

输入格式

见题面

输出格式

见题面

样例输入
981 829 468 361 696 306 256 324 789 613 528 39 587 905 351 921 293 364 291 555 57 832 601 934 500 621 844 323 62 67 731 812 873 693 506 32 575 817 156 624 923 901 839 158 109 971 20 755 701 697 242 549 834 414 165 279 798 511 259 642 629 318 940 54 594 470 236 371 763 524 658 479 591 36 93 787 428 896 948 690 207 854 805 659 452 917 106 785 847 781 668 217 447 212 21 708 229 349 889 776 2 339 398 436 663 609 357 425 186 353 840 33 141 313 843 163 254 183 171 266 51 981 676 922 650 405 662 22 124 151 882 525 192 322 272 26 704 890 819 904 496 360 297 979 232 144 617 302 431 157 400 445 140 636 99 387 7 45 665 606 540 393 121 826 908 550 719 565 899 895 81 115 700 412 504 202 160 369 514 98 562 188 865 434 746 421 608 576 278 44 173 78 508 945 937 800 855 857 823 644 942 801 315 331 859 603 810 673 497 284 374 457 423 143 725 544 522 713 682 610 117 304 691 294 784 359 951 510 77 829 786 330 559 108 907 225 954 589 862 628 568 561 816 793 443 15 718 953 303 572 622 556 216 271 779 79 661 614 641 627 692 134 892 102 949 432 709 795 861 309 858 774 584 399 648 253 342 616 440 219 214 84 695 257 748 502 329 363 933 567 403 828 551 670 808 950 230 426 577 420 851 310 391 625 407 926 619 830 204 707 402 28 573 283 879 527 332 136 679 736 453 935 105 488 726 582 860 8 523 200 100 317 651 65 790 61 377 298 427 133 269 887 722 394 437 632 223 977 769 23 815 75 72 874 902 520 822 114 184 541 936 768 435 507 741 406 48 932 674 267 10 968 765 739 538 350 132 526 316 856 976 811 337 166 738 880 640 852 449 792 4 390 516 930 251 620 543 480 56 319 762 280 92 753 564 362 547 139 101 196 848 499 546 274 193 321 804 29 365 460 653 566 916 492 743 373 871 671 25 728 1 367 127 122 383 788 531 782 837 424 145 723 867 209 978 809 473 265 512 224 299 276 64 308 462 228 742 571 960 314 944 706 633 95 58 172 864 974 703 429 588 174 814 90 791 961 68 870 720 159 69 43 419 724 638 717 27 518 149 733 16 194 6 50 118 179 110 3 71 305 201 148 745 825 943 623 554 596 244 558 392 898 113 199 850 285 261 875 498 630 416 539 87 422 910 5 557 418 711 465 86 797 268 586 35 957 486 845 678 131 956 125 327 380 370 430 409 975 169 481 927 30 545 836 215 411 289 52 24 335 626 475 928 807 37 772 675 941 764 433 368 234 883 146 849 442 177 884 657 652 533 74 478 248 654 893 180 552 631 794 963 581 104 221 356 264 920 635 759 300 17 438 702 404 842 747 521 835 758 649 821 203 448 467 495 375 70 120 38 946 647 685 686 656 618 379 382 9 142 761 396 31 799 168 135 869 542 195 780 888 260 190 802 767 751 806 487 677 155 210 505 83 783 474 388 639 458 175 684 477 600 579 459 14 517 343 732 503 903 646 563 245 959 347 593 197 198 296 334 912 766 46 243 553 952 167 352 744 866 191 178 307 536 931 710 389 80 187 972 580 119 607 128 47 378 255 683 249 515 918 962 161 749 290 841 938 164 773 537 258 919 41 615 446 287 925 489 727 233 376 752 958 885 441 189 585 366 150 491 208 206 699 735 147 583 740 176 655 55 263 107 698 535 226 737 578 770 344 401 301 501 211 838 354 182 220 218 602 326 333 965 116 484 311 408 939 286 466 417 846 574 355 162 570 906 509 716 824 820 775 288 569 868 40 813 529 91 395 980 386 96 372 241 340 463 611 760 750 358 170 694 878 19 490 734 929 292 532 833 213 63 967 915 947 612 712 336 560 341 246 913 270 827 530 730 82 455 348 59 924 76 605 483 66 450 592 597 469 381 771 153 295 666 756 513 60 137 235 385 637 729 346 338 415 494 222 73 590 89 818 231 247 85 275 757 660 476 129 42 872 345 439 911 548 94 688 493 964 881 262 238 472 328 112 397 320 454 689 227 130 103 598 714 88 252 461 796 451 281 519 900 863 237 154 111 410 205 645 464 138 664 273 13 444 471 325 966 894 778 669 34 604 595 721 185 754 97 126 970 886 643 534 876 181 240 11 831 482 715 897 53 891 777 955 667 239 914 853 969 456 599 282 312 680 681 49 877 705 973 672 250 384 634 687 152 909 12 803 277 413 485 123 18 552 r 342 r 7 r 856 r 941 r 167 r 311 r 689 r 251 l 564 r 332 r 234 l 169 r 948 l 642 r 469 r 65 r 14 r 826 r 278 r 903 r 832 l 550 l 873 r 2 r 258 r 332 l 917 r 470 r 961 r 754 r 690 r 164 r 489 l 635 r 653 r 836 l 523 l 301 r 323 l 406 r 552 r 684 r 566 r 314 r 976 r 572 r 390 l 402 r 141 r 622 r 349 r 151 r 97 r 150 r 822 r 608 l 824 l 114 r 788 r 253 l 65 r 341 r 485 r 828 r 374 r 443 r 273 r 194 l 323 r 695 r 200 r 455 r 332 r 967 r 757 r 128 l 54 r 495 r 543 r 423 r 416 r 74 r 132 l 939 r 168 l 411 r 445 l 24 r 549 r 693 r 472 r 435 r 658 r 20 r 412 r 201 r 937 r 882 r 970 r 194 l 215 r 26 r 447 r 222 r 792 r 624 r 897 r 796 r 95 r 55 r 366 l 608 l 191 l 410 r 450 l 869 l 437 r 275 r 164 r 601 r 613 r 488 l 965 r 62 r 400 r 536 r 369 l 302 r 404 r 414 r 627 r 184 r 721 r 88 l 552 l 694 l 725 r 818 r 159 r 867 r 942 r 731 r 501 l 545 l 846 r 53 r 391 r 500 r 48 r 75 r 405 r 118 r 603 r 866 l 762 r 29 r 728 r 303 l 183 l 120 r 329 r 166 r 249 r 376 l 430 l 320 r 810 r 751 r 470 r 631 r 638 r 723 r 807 r 6 l 295 r 192 r 926 r 233 r 683 r 636 l 974 r 582 r 764 l 424 r 349 l 12 r 707 r 544 l 920 r 444 r 340 r 964 l 301 r 589 r 185 l 795 r 149 l 827 r 393 r 923 l 843 r 320 r 754 l 454 r 733 r 17 r 207 r 329 r 973 r 122 r 72 r 337 l 522 r 8 r 289 r 358 r 177 r 105 r 629 r 955 r 689 l 832 r 23 l 823 l 500 r 205 r 801 l 510 r 736 r 544 l 882 r 95 r 190 r 800 r 645 r 571 r 698 r 857 r 564 r 166 l 423 l 338 r 563 r 904 r 583 r 885 r 772 r 611 l 114 r 181 l 293 l 804 r 15 r 476 l 138 l 862 l 429 r 69 r 382 r 39 l 319 l 606 l 275 r 550 r 967 r 495 l 263 r 653 r 453 r 541 l 211 r 406 r 777 r 520 r 877 r 183 r 584 r 918 l 96 r 642 l 92 r 608 l 115 l 436 r 958 r 518 r 980 r 650 r 813 r 153 l 598 r 141 r 446 r 856 r 348 l 920 l 739 r 356 l 728 r 559 r 703 l 325 r 249 l 224 l 155 r 651 l 3 r 893 r 64 l 159 l 147 r 152 r 582 r 136 r 639 l 800 r 486 l 176 r 31 l 273 l 981 l 57 r 128 r 529 l 862 l 19 l 95 r 57 r 524 r 722 l 870 r 924 l 200 r 571 r 343 l 314 l 282 l 291 r 973 r 132 l 261 r 77 r 56 r 73 l 26 r 821 l 168 r 893 r 127 r 196 r 422 r 6 r 381 r 748 l 246 r 552 r 897 l 666 r 292 l 7 r 150 l 278 r 920 r 941 l 807 l 964 r 173 r 393 r 409 r 637 r 9 r 699 r 185 l 596 r 394 r 4 l 845 r 930 l 903 r 227 r 606 r 617 r 800 l 208 r 96 r 181 l 850 r 557 r 254 r 667 r 854 l 316 r 43 l 315 r 98 r 336 r 116 r 546 r 600 r 414 r 496 l 266 r 261 r 39 r 936 l 784 r 591 r 285 r 833 r 616 r 542 r 22 r 403 r 889 r 257 r 375 l 372 r 22 r 168 r 126 r 412 r 827 r 261 r 759 r 812 r 503 r 496 r 961 r 374 r 196 r 618 l 880 l 551 r 434 l 532 l 637 r 573 l 151 r 84 r 267 l 398 r 649 r 627 l 267 l 617 l 92 r 31 l 467 r 774 l 700 l 126 r 379 r 18 l 490 l 727 r 360 l 7 l 574 r 917 r 828 r 849 r 33 l 911 r 968 r 328 r 884 r 94 l 469 r 579 l 598 r 124 l 452 l 666 r 297 r 406 r 221 r 973 r 225 l 956 r 599 r 696 l 1 r 811 r 674 r 821 l 218 r 645 r 510 l 554 r 728 r 356 r 865 r 761 l 409 r 806 r 745 r 206 r 364 r 263 r 366 l 212 r 602 l 461 r 854 r 275 l 192 l 630 r 592 r 816 r 338 r 896 r 109 l 874 r 807 r 285 r 408 r 966 l 79 l 874 r 623 l 527 l 320 r 182 r 780 r 501 r 850 r 810 r 230 r 586 l 234 l 432 r 186 r 75 r 537 l 254 r 746 l 47 r 504 r 565 l 267 r 100 r 332 l 939 r 486 l 459 l 92 r 511 r 870 l 699 r 431 l 390 r 506 r 319 r 94 l 767 r 830 r 431 r 376 r 602 l 672 l 416 l 462 r 474 r 192 r 470 r 386 r 460 r 548 r 172 r 675 r 211 r 366 r 903 r 499 r 657 l 425 r 731 r 469 l 621 l 33 r 789 r 493 r 975 r 295 r 826 r 587 r 572 r 688 r 755 r 724 r 586 r 789 r 861 r 618 l 544 l 866 r 635 l 980 l 674 l 908 r 601 r 257 r 670 r 829 l 391 l 151 r 866 l 64 l 921 l 581 r 597 l 543 r 181 l 666 r 480 r 882 l 9 r 715 r 706 l 313 r 940 r 964 l 690 r 855 l 951 r 261 r 187 l 378 l 231 r 926 l 643 r 539 r 561 r 335 l 481 r 743 r 268 l 686 r 530 r 303 l 265 r 639 l 6 l 210 r 193 l 507 l 410 l 605 l 674 r 643 r 920 r 523 l 460 r 229 r 151 r 234 l 291 r 430 r 763 r 882 r 651 r 319 r 18 l 145 r 428 r 5 r 445 r 358 r 388 r 531 r 225 r 126 r 295 r 708 r 388 r 775 r 158 r 174 r 748 r 37 r 610 r 97 r 761 r 507 r 370 l 574 r 950 r 899 r 431 r 603 r 116 r 132 r 599 l 544 r 924 l 799 l 924 l 23 r 855 l 368 l 686 r 230 r 542 l 259 r 678 r 720 r 369 l 844 r 773 l 25 r 518 r 835 r 935 r 433 r 336 l 265 l 20 l 546 r 218 l 896 l 465 r 868 l 181 r 26 r 826 l 378 l 398 l 40 r 72 r 280 l 962 r 710 r 545 r 820 l 107 r 220 r 247 l 169 r 918 l 292 r 723 r 415 l 109 l 405 r 305 r 444 l 823 l 655 r 626 r 634 l 764 l 529 r 474 l 141 r 504 r 776 r 597 l 686 r 407 r 267 l 927 l 647 r 693 l 428 r 186 r 107 r 596 r 947 r 977 r 71 l 593 r 24 l 243 r 571 r 258 l 250 l 539 l 378 r 354 r 853 r 186 r 581 r 804 r 154 r 701 l 543 r 162 r 859 r 320 r 664 r 980 r 209 r 882 r 858 r 86 r 961 r 77 l 516 r 963 l 582 l 489 r 224 l 441 r 854 l 183 r 587 r 107 r 765 r 217 r 254 r 575 l 169 l 324 l 663 r 953 r 317 r 719 r 634 r 493 l 336 r 914 r 651 r 407 r 498 r 301 r 116 r 250 r 826 l
样例输出
984213