Задача №115436. Роботы-исследователи
Поле для испытания роботов состоит из \(n\) полей, пронумерованных от \(1\) до \(n\) слева направо. На каждом поле написана буква английского алфавита, при прочтении букв на полях от первого до \(n\)-го получается строка \(s\).
Есть два робота, которые могут передвигаться по полю, при этом:
- роботам известна строка \(s\);
- роботы могут свободно обмениваться информацией;
- роботы всегда знают расстояние между ними, а также какой из роботов находится левее, а какой правее;
- каждый из двух роботов может прочитать букву, которая находится под ним;
За один шаг робот может, обменявшись информацией с другим роботом, переместиться на соседнее поле слева или на соседнее поле справа. При этом, если робот пытается переместиться левее первого или правее \(n\)-го поля, то он уничтожается.
Ученые хотят провести \(q\) экспериментов, в \(i\)-м из которых первого робота ставят на позицию \(x_i\), а второго на позицию \(y_i\). Цель роботов в каждом из экспериментов — посетить как можно больше различных полей. Для каждого эксперимента необходимо определить, какое максимальное количество полей смогут посетить роботы, не рискуя уничтожением.
В первой строке указана пара чисел \(n\) и \(q\) (\(1 \le n,q \le 300\,000\)) — количество полей и количество экспериментов.
Во второй строке указана строка \(s\) длины \(n\), состоящая из \(n\) строчных букв латинского алфавита.
В последующих \(q\) строках указаны пары чисел \(x_i\), \(y_i\) (\(1 \le x_i , y_i \le n\)).
Для каждого из экспериментов выведите наибольшее количество различных полей, которое смогут посетить роботы.
Рассмотрим последний эксперимент в примере. Роботы стартуют в одной точке и видят букву « a ». Они понимают, что двигаться влево опасно, это может привести к уничтожению робота. Однако двигаться направо безопасно, так как последняя буква строки — « b ». Один или оба робота двигаются вправо, пока не окажутся на букве « b ». Оказавшись на букве « b », роботы понимают, что только что считали строку « aab », эта строка может быть как началом, так и концом строки, выйти за ее пределы, не рискуя уничтожением, они не могут, поэтому всего удалось посетить всего \(3\) поля.
10 4 aabaabbaab 4 5 8 5 2 3 1 1
3 10 3 3