Масив символів і майже паліндроми#227

Масив символів і майже паліндроми

4 секунди

256 мегабайтів

Дуже складна

Це інтерактивна задача.

Рядок вважається паліндромом, якщо він читається однаково з обох сторін. Формально, рядок $s$ довжини $n$ вважається паліндромом, якщо $s_{i} = s_{n - i + 1}$ s_i = s_{n-i+1} для $1 \leq i \leq n$ 1 \le i \le n. Наприклад, рядки «gg», «ara», «abacaba», «rotator» є паліндромами, а рядки «array», «palindrome», «uoi» — ні.

Назвемо рядок майже паліндромом, якщо в ньому можна переставити символи так, щоб він став паліндромом. Наприклад, рядки «n», «ara», «arr», «array» є майже паліндромами, а рядки «palindrome», «uoi», «random» — ні.

Підрядком рядка вважається рядок, який може бути утворений за допомогою видалення деякої (можливо нульової) кількості елементів з його початку та кінця.

Визначимо $f (s)$ як максимальну довжину серед довжин підрядків $s$ , які не є майже паліндромами, або $0$ , якщо таких підрядків немає.

Задано рядок $s$ довжини $n$ , що складається з маленьких літер латинського алфавіту. Також задано $q$ запитів виду $l_{i}$ l_i, $r_{i}$ r_i. Для кожного запиту знайдіть значення $f (s [l_{i} .. r_{i}])$ f(s[l_i..r_i]), де $s [l_{i} .. r_{i}]$ s[l_i..r_i] позначає підрядок, що складається з символів $s_{l_{i}}, s_{l_{i} + 1}, \dots, s_{r_{i}}$ s_{l_i}, s_{l_{i} + 1}, \ldots, s_{r_i}.

Вхідні дані

У першому рядку задано одне ціле число $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \le n \le 2\cdot 10^5) — довжина рядка.

У другому рядку задано рядок $s$ , що складається з $n$ маленьких літер латинського алфавіту.

У третьому рядку задано одне ціле число $q$ ( $1 \leq q \leq 2 \cdot 1 0^{5}$ 1\le q \le 2\cdot 10^5) — кількість запитів.

У четвертому рядку задано два цілі числа $l_{1}, r_{1}$ l_1, r_1 ( $1 \leq l_{1} \leq r_{1} \leq n$ 1 \leq l_1 \leq r_1 \leq n) — параметри першого запиту.

Параметри наступних запитів ви отримаєте від програми журі (див. розділ «Протокол взаємодії»).

Взаємодія

Програма журі виводитиме у окремих рядках по два цілі числа $l_{i}$ l_i, $r_{i}$ r_i ( $1 \leq l_{i} \leq r_{i} \leq n$ 1\le l_i\le r_i\le n) — параметри чергового запиту, починаючи з другого.

Програма журі не виведе параметри чергового запиту, доки не прочитає відповідь вашої програми на попередній запит.

Подбайте про виклик методу flush після виводу кожного рядка. Для цього можна використовувати:

fflush(stdout), cout << endl або cout.flush() в C++;
System.out.flush() в Java;
flush(output) в Pascal;
sys.stdout.flush() в Python;
дивіться документації для інших мов програмування.

Вихідні дані

Для $i$ -го запиту в окремому рядку виведіть одне ціле число — шукане значення $f (s [l_{i} .. r_{i}])$ f(s[l_i..r_i]).

Приклади

Приклад

8
aabaaaba
3
3 7
1 8
4 4

4
6
0

Примітка

У першому прикладі необхідно знайти відповіді на три запити:

$s [3..7] =$ s[3..7] =\;«baaab», підрядком якого є рядок «aaab» довжини 4, який не є майже паліндромом;
$s [1..8] =$ s[1..8] =\;«aabaaaba», підрядком якого є рядок «aabaaa» довжини 6, який не є майже паліндромом;
$s [4..4] =$ s[4..4] =\;«a», усі підрядки якого є майже паліндромами.

Оцінювання

( $6$ балів): $q = 1$ q=1, $l_{1} = 1$ l_1=1, $r_{1} = n$ r_1=n, $n$ — парне, $s$ має вигляд «aabbaabbaa...»;
( $9$ балів): $q = 1$ q=1, $l_{1} = 1$ l_1=1, $r_{1} = n$ r_1=n, $n \leq 200$ n \le 200;
( $5$ балів): $q = 1$ q=1, $l_{1} = 1$ l_1=1, $r_{1} = n$ r_1=n, $n \leq 5000$ n \le 5000;
( $8$ балів): $q = 1$ q=1, $l_{1} = 1$ l_1=1, $r_{1} = n$ r_1=n;
( $10$ балів): $s$ містить лише літери a та b;
( $8$ балів): $s_{l_{i}} \neq = s_{r_{i}}$ s_{l_i} \neq s_{r_i} для $1 \leq i \leq q$ 1 \le i \le q;
( $7$ балів): $s_{i} \neq = s_{i + 1}$ s_i \neq s_{i+1} для $1 \leq i < n$ 1 \le i < n;
( $10$ балів): $s$ містить лише літери a, b, c, d, e та f;
( $18$ балів): $(r_{i} - l_{i} + 1)$ (r_i-l_i+1) — непарне для $1 \leq i \leq q$ 1\le i\le q;
( $19$ балів): без додаткових обмежень.