Пакування сірників#1435

Пакування сірників

4 секунди

64 мегабайти

Середня

Дівчинка Таня за допомогою гравців Test-the-Best все ж таки змогла підрахувати, скільки їй потрібно коробок, щоб виконати домашнє завдання. Але прийшов її молодший брат Петя і чомусь розклав деякі сірники в ряд на столі. Тепер Таня хоче його покарати — змусити зібрати сірники назад у коробки. Дівчинка вона примхлива і хоче, щоб брат зібрав не всі сірники, а лише сірники з номерами від $X$ до $Y$ включно (сірники нумеруються зліва направо послідовними цілими числами, починаючи з нуля), а всі інші сірники Таня попередньо скине зі столу на підлогу (про реакцію тата на дії Тані умова задачі замовчує :) ).

Також Таня хоче накласти суворі вимоги на те, в якому порядку і скільки сірників Петя має брати зі столу. Вимоги ці такі: за один раз брат повинен взяти якнайбільше поспіль лежачих сірників однакової довжини, причому серед них обов'язково має бути сірник з мінімальним номером.

З якихось незрозумілих причин Таню цікавить, яку максимальну кількість сірників за один раз візьме Петя зі столу під час процесу збору сірників. Порахувати цю величину вона попросила вас. Оскільки з значеннями $X$ та $Y$ Таня ще остаточно не визначилась, то провести підрахунки потрібно буде одразу для декількох пар $(X, Y)$ (X, Y).

Вхідні дані

Перший рядок задає зліва направо довжини сірників, що лежать на столі. Кожний символ цього рядка — цифра '1'..'9', яка визначає довжину відповідного сірника. Рядок містить від $1$ до $100000$ символів включно.

Другий рядок містить розділений одинарними пробілами список пар $(X, Y)$ (X, Y), для яких потрібно порахувати величину, що цікавить Таню. Кожна пара описується у вигляді "(X, Y)". Рядок містить від $1$ до $10000$ пар.

Вихідні дані

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

Приклади

Приклад 1

Примітка

Sample 1

У всіх $4$ випадках Петя зможе за один раз узяти зі столу всі сірники.

Sample 2

У всіх $4$ випадках Петя щоразу братиме зі столу по одному сірнику.

Sample 3

1-й випадок: $X = 1, Y = 5$ X = 1, Y = 5. Перед Петею залишаться сірники ${2, 3, 3, 3, 4}$ \{2, 3, 3, 3, 4\}. Спочатку він візьме один сірник довжини $2$ , потім $3$ сірники довжини $3$ і, нарешті, один сірник довжини $4$ . Максимальна кількість взятих за раз сірників — $3$ .

2-й випадок: $X = 0, Y = 13$ X = 0, Y = 13. Перед Петею залишаться всі сірники. На $5$ -му кроці він візьме $4$ сірники довжини $2$ .

3-й випадок: $X = 2, Y = 7$ X = 2, Y = 7. Перед Петею залишаться сірники ${3, 3, 3, 4, 2, 2}$ \{3, 3, 3, 4, 2, 2\}. І, як ви вже, мабуть, самі здогадалися, спочатку він візьме $3$ сірники довжини $3$ , потім один сірник довжини $4$ і в кінці $2$ останніх сірники довжини $2$ .