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

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


 

Дата сайнс

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

Назовём последовательность чисел xi пилообразной, если x1 > x2 < x3 > x4 < … или x1< x2 > x3 < x4 > … (заметим, что последовательность из одного числа и последовательность из двух различных чисел являются пилообразными).

Назовём хаотичностью последовательности xi наибольшее число k такое, что можно удалить некоторые числа из x и оставшиеся будут образовывать пилообразную последовательность размера k.

Михаилу, начинающему дата-саентисту, необходимо обработать данные, представленные в виде массива n различных чисел ai. Есть два типа запросов к данным:

  • «! i x» – установить ai равным x (гарантируется, что после этого все ai будут различны);
  • «? l r» – вычислить хаотичность отрезка a[l…r], то есть последовательности al, al+1, …, ar;

По загадочным обстоятельствам Михаил больше не будет программировать алгоритмы, поэтому ему нужна ваша помощь в обработке данных.

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

Первая строка входного файла INPUT.TXT содержит целое число n – размер данных (1 ≤ n ≤ 2×105).

Вторая строка содержит n целых чисел ai (1 ≤ ai ≤ 109).

Третья строка содержит целое число q – количество запросов (1 ≤ q ≤ 3×105).

В каждой из следующих q строк содержится описание запроса в формате, описанном выше. Для запросов изменения выполняется 1 ≤ i ≤ n и 1 ≤ x ≤ 109. Для запросов на отрезке выполняется 1 ≤ l ≤ r ≤ n.

Гарантируется, что в любой момент a состоит из попарно различных чисел.

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

В выходной файл OUTPUT.TXT для каждого запроса второго типа (то есть начинающегося с «?») в порядке их поступления на вход выведите в новой строке одно целое число – ответ на этот запрос.

Пример

INPUT.TXTOUTPUT.TXT
16
1 6 2 5 3 4
7
? 1 6
? 2 5
! 1 9
! 4 1
? 1 4
! 1 5
? 1 6
6
4
2
4

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


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

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



Домен fidanian.ru: купить в магазине доменных имен Рег.ру