#E74622. 简单的二分

简单的二分

Background

第一周的训练就结束了,可乐加冰和他的队友给大家出了点有趣的题,编程之路才刚刚开始,大家加油。!!!!在周赛千万不要爆0哦!!!!!!

Description

现在给你一个长度为n的有序的数组串,可乐加冰希望你能根据他的m条指令来进行相应的搜索查找,你能够帮他完成吗。如果可乐加冰说‘L’和一个数字X,那么请你找出这列数组中第一次出现X他的数组下标,如果可乐加冰说‘R’和一个数字X,那么请你找出这列数组中最后一次出现这个X他的数组下标。如果没有这个数,请你输出‘-1’; ps:下标从0开始!!!!!!

Input

第一行输入一个n,m,n表示数组长度,m表示可乐加冰的指令条数; 第二行输入一个长度为n的; 之后m行输入一个字符ch,和一个数字x表示要找的数

Output

输出m行,x被要求的下标或者“-1”

Samples

6 3
1 2 3 4 4 5
L 4
R 4
R 0
3
4
-1

Limitation

1s, 1024KiB for each test case.