Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Камни

(Время: 3 сек. Память: 32 Мб Сложность: 62%)

Перед Бобом выложены в ряд n черных камней, пронумерованных от 1 до n. На i-м камне записано целое число ai. Для каждого числа от 1 до n известно, что оно записано ровно на одном камне, иными словами числа ai образуют перестановку. Будем называть соседними для i-го камня (i-1)-й и (i+1)-й камни (если они существуют).

Боб выполняет следующие n шагов:

  • На первом шаге Боб выбирает произвольное i от 1 до n и красит i-й камень в белый цвет.
  • На шагах с номерами от 2 до n Боб смотрит на такие черные камни, которые являются соседними для хотя бы одного белого камня, из них он выбирает камень j с минимальным aj и красит его в белый цвет.

Несложно заметить, что к концу выполнения всех шагов перед Бобом будут лежать n белых камней.

Алиса выбрала q пар значений pj и kj. Для каждой пары она хочет выяснить, сколько существует различных способов выбрать камень на первом шаге, которые приведут к тому, что камень с номером pj станет белым ровно на kj-м шаге.

Помогите Бобу ответить на q запросов Алисы.

Входные данные

В первой строке входного файла INPUT.TXT заданы числа n и q – количество камней и запросов соответственно (2 ≤ n ≤ 105; 1 ≤ q ≤ 105).

Во второй строке заданы записанные на камнях целые числа a1, a2, ..., an (1 ≤ ai ≤ n, все ai различны).

В следующих q строках заданы запросы, j-й запрос задается парой целых чисел pj и kj (1 ≤ pj ≤ n, 1 ≤ kj ≤ n) – номером камня и номером шага, на котором этот камень должен быть покрашен в белый цвет.

Выходные данные

Для каждого запроса в выходной файл OUTPUT.TXT в отдельной строке выведите количество значений i, таких что если i-й камень будет покрашен в белый цвет на первом шаге, то pj-й камень покрасится в белый цвет на kj-м шаге.

Примеры

INPUT.TXTOUTPUT.TXT
16 4
1 4 6 5 2 3
3 1
2 2
6 3
4 3
1
2
1
2
25 3
5 2 3 4 1
2 3
4 4
3 2
0
1
1

Пояснение к примеру

В первом тестовом примере операции выполняются следующим образом:

  • Если на первом шаге был выбран 1-й камень: 1-й шаг: [1, 4, 6, 5, 2, 3], 2-й шаг: [1, 4, 6, 5, 2, 3], 3-й шаг: [1, 4, 6, 5, 2, 3], 4-й шаг: [1, 4, 6, 5, 2, 3], 5-й шаг: [1, 4, 6, 5, 2, 3], 6-й шаг: [1, 4, 6, 5, 2, 3].
  • Если на первом шаге был выбран 2-й камень: 1-й шаг: [1, 4, 6, 5, 2, 3], 2-й шаг: [1, 4, 6, 5, 2, 3], 3-й шаг: [1, 4, 6, 5, 2, 3], 4-й шаг: [1, 4, 6, 5, 2, 3], 5-й шаг: [1, 4, 6, 5, 2, 3], 6-й шаг: [1, 4, 6, 5, 2, 3].
  • Если на первом шаге был выбран 3-й камень: 1-й шаг: [1, 4, 6, 5, 2, 3], 2-й шаг: [1, 4, 6, 5, 2, 3], 3-й шаг: [1, 4, 6, 5, 2, 3], 4-й шаг: [1, 4, 6, 5, 2, 3], 5-й шаг: [1, 4, 6, 5, 2, 3], 6-й шаг: [1, 4, 6, 5, 2, 3].
  • Если на первом шаге был выбран 4-й камень: 1-й шаг: [1, 4, 6, 5, 2, 3], 2-й шаг: [1, 4, 6, 5, 2, 3], 3-й шаг: [1, 4, 6, 5, 2, 3], 4-й шаг: [1, 4, 6, 5, 2, 3], 5-й шаг: [1, 4, 6, 5, 2, 3], 6-й шаг: [1, 4, 6, 5, 2, 3].
  • Если на первом шаге был выбран 5-й камень: 1-й шаг: [1, 4, 6, 5, 2, 3], 2-й шаг: [1, 4, 6, 5, 2, 3], 3-й шаг: [1, 4, 6, 5, 2, 3], 4-й шаг: [1, 4, 6, 5, 2, 3], 5-й шаг: [1, 4, 6, 5, 2, 3], 6-й шаг: [1, 4, 6, 5, 2, 3].
  • Если на первом шаге был выбран 6-й камень: 1-й шаг: [1, 4, 6, 5, 2, 3], 2-й шаг: [1, 4, 6, 5, 2, 3], 3-й шаг: [1, 4, 6, 5, 2, 3], 4-й шаг: [1, 4, 6, 5, 2, 3], 5-й шаг: [1, 4, 6, 5, 2, 3], 6-й шаг: [1, 4, 6, 5, 2, 3].

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 2022 / 2023
 2023 / 2024
 A. Разделение прямоугольника
 B. Произведение Фибоначчи
 C. Робот-пылесос
 D. Разноцветные точки
 E. Метрострой
 F. Красивые последовательности
 G. Камни
 H. Обыкновенная задача про строки

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru