Язык программирования

 

Примеры

№	Входные данные	Выходные данные
1	3 4 1 2 3 4 5 6 7 8 9 10 11 12 9 4 1 1 2 3 3 1 4	24

Улица М. города Д. печально известна среди местных жителей качеством дорожного покрытия. В этом тяжело винить ремонтные службы: пожалуй, они следят за этой улицей даже слишком тща- тельно. Проблема в том, что каждый без исключения ремонт улицы выглядит следующим образом: бригада рабочих выбирает некоторый участок улицы единичной длины и меняет асфальт только на нём, причём тип асфальта на этом участке в результате может отличаться от типов асфальта на других участках, что, разумеется, усложняет проезд по улице.

Вы, как коренной житель города Д. и программист по призванию, решили использовать свои профессиональные навыки на благо общества и облегчить жизнь своим соседям по улице М. А именно, вы решили создать сайт, содержащий актуальную информацию о непроходимости улицы. Прежде всего, вы заметили, что улица разбита на N идущих друг за другом участков единичной длины. По странному совпадению бригада рабочих всегда выбирает для ремонта ровно один из таких участков и целиком меняет тип асфальта на нём. Затем вы пронумеровали эти участки от 1 до N и собрали информацию о типе асфальта на каждом из участков — числа t1, t2, . . . , tN (ti — номер типа асфальта на i-м участке, согласно Государственному реестру дорожных покрытий). Наконец, вы определили непроходимость улицы как минимальное количество непрерывных непересекающихся отрезков c одинаковым типом асфальта, на которые она разбивается. Например, непроходимость улицы 110111 равна 3, потому что она состоит из трёх участков 11, 0 и 111, а идеальная улица 2222 имеет непроходимость, равную 1.

Казалось бы, достаточно вычислить и разместить на сайте текущую величину непроходимости улицы, и жители будут довольны? К сожалению, асфальт меняют довольно часто, и вам не хочется каждый раз выходить на улицу и заново собирать данные. Поэтому вы дали возможность жителям сообщать на вашем сайте об обновлении дорожного покрытия. Дело осталось за малым — научиться обновлять после каждого такого сообщения актуальную величину непроходимости улицы.

Формат входных данных
Первая строка входного файла содержит единственное натуральное число N — количество участ- ков дороги (1 <= N <= 100 000). Следующая строка содержит N целых чисел t1, t2, . . . , tN — исходные типы асфальта участков дороги (|ti | <= 109 ). Третья строка содержит единственное натуральное число Q — количество сообщений от жителей об обновлении дорожного покрытия (1 <= Q <= 100 000). Каждая из следующих Q строк содержит очередное сообщение. i-е сообщение представляет собой пару целых чисел pi , ci — номер ремонтируемого участка дороги и новый номер типа асфальта на этом участке (1 <= pi <= N, |ci | <= 109 ). Участки дороги нумеруются от 1 до N в порядке задания их исходного типа асфальта во второй строке входного файла.

Формат выходных данных
Выведите Q строк. i-я строка (1 <= i <= Q) должна содержать единственное целое число — величину непроходимости улицы после первых i обновлений дорожного покрытия.

Примеры

Ввод	Вывод
5 2 2 2 2 2 5 1 2 2 3 4 3 3 1 3 3	1 3 5 5 3
7 1 1 2 3 2 2 1 3 2 2 4 2 6 9	5 3 4

Замечание
Рассмотрим подробнее второй тестовый пример. Изначально улица 1123221 состоит из 5 отрезков с одинаковым типом асфальта: 11, 2, 3, 22, 1 и, соответственно, имеет непроходимость, равную 5 (её не нужно выводить в выходной файл).
После первого ремонта улица станет выглядеть как 1223221 и всё ещё будет состоять из 5 участ- ков, но других: 1, 22, 3, 22, 1. Поэтому её непроходимость равна 5, и первое число в выходном файле равно 5.
После второго ремонта улица будет состоять из 3 участков: 1, 22222, 1, так что второе число в выходном файле — 3.
После третьего ремонта получим 4 участка: 1, 2222, 9, 1, соответственно, третье и последнее число в выходном файле — 4.

Какая из ссылок является смешанной?

1. F2
2. $F$3
3. F$3
4. $F$4

Какая из ссылок является относительной?

1. F2
2. $F$3
3. F$3
4. $F4

Какая из ссылок является абсолютной?

1. F2
2. $F$3
3. F$3
4. $F4

Если ячейке задается текстовый формат, то содержимое ячейки автоматически выравнивается

1. по центру
2. по ширине
3. по правому краю
4. по левому краю

Какой формат задан всем ячейкам по умолчанию?

1. числовой
2. текстовый
3. денежный
4. общий

Какой формат может содержать любую последовательность символов?

1. числовой
2. текстовый
3. денежный
4. процентный

Элементарный элемент таблицы называется

1. столбцы
2. строки
3. ячейка
4. диапазон ячеек

Все ячейки, расположенные на одном вертикальном уровне таблицы, называются

1. столбцы
2. строки
3. ячейка
4. диапазон ячеек

Все ячейки, расположенные на одном горнизонтальном уровне таблицы, называются

1. столбцы
2. строки
3. ячейка
4. диапазон ячеек

Если раскопировать формулу влево или вправо, то в формуле будет меняться

1. номер столбца
2. номер строки
3. номер столбца и номер строки
4. в зависимости от направления копирования

Если раскопировать формулу вниз или вверх, то в формуле будет меняться

1. номер столбца
2. номер строки
3. номер столбца и номер строки
4. в зависимости от направления копирования

К каому типу относится данная ссылка: $А$2

1. абсолютная
2. относительная
3. смешанная
4. гиперссылка

К каому типу относится данная ссылка: $А2

1. абсолютная
2. относительная
3. смешанная
4. гиперссылка

Комплекс программ, предназначенный для автоматизации вычислений и анализа данных, представленных в табличной форме называется...

1. электронной таблицей
2. табличным редактором
3. электронным редактором таблиц
4. табличным процессором

Каково основное назначение табличного процессора?

1. представление числовой информации в табличной форме
2. создание таблиц и диаграмм
3. автоматизация расчетов в таблицах
4. создание таблиц

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

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

Друзья заметили, что выполняется следующее условие: если загадать некоторую станцию X и выписать для нее два числа: Da — расстояние от станции, на которой живет Андрей, до станции X и Db — расстояние от станции, на которой живет Борис, до станции X, то полученная пара чисел [Da, Db] будет однозначно задавать станцию X.

Например, если n = 4, Андрей живет на станции 1, а Борис живет на станции 2, то станция 1 задается парой [0, 1], станция 2 — парой [1, 0], станция 3 — парой [2, 1] и станция 4 — парой [1, 2].

Их одноклассник Сергей живет в соседнем городе и не знает, на каких станциях живут Андрей и Борис. Чтобы найти друзей, он заинтересовался, сколько существует вариантов пар станций A, B, таких что если Андрей живет на станции A, а Борис — на станции B, то выполняется описанное выше условие.

Требуется написать программу, которая по числу станций n на кольцевой линии определяет искомое количество вариантов.

Формат входного файла
Первая строка входного файла содержит одно целое число n (3 ≤ n ≤ 40 000).
Формат выходного файла
Выходной файл должен содержать одно число — искомое количество вариантов.

Примеры входных и выходных файлов

Ввод	Вывод
4	8
5	20

Пояснения к примерам
В первом примере подходят следующие варианты:
- Андрей живет на станции 1, а Борис на станции 2;
- Андрей живет на станции 1, а Борис на станции 4;
- Андрей живет на станции 2, а Борис на станции 1;
- Андрей живет на станции 2, а Борис на станции 3;
- Андрей живет на станции 3, а Борис на станции 2;
- Андрей живет на станции 3, а Борис на станции 4;
- Андрей живет на станции 4, а Борис на станции 1;
- Андрей живет на станции 4, а Борис на станции 3.
 

Для проведения церемонии открытия олимпиады по информатике организаторы осуществляют поиск подходящего зала. Зал должен иметь форму прямоугольника, длина каждой из сторон которого является целым положительным числом.
Чтобы все участники церемонии поместились в зале, и при этом он не выглядел слишком пустым, площадь зала должна находиться в пределах от A до B квадратных метров, включительно.
Чтобы разместить на стенах зала плакаты, рассказывающие об успехах школьников на олимпиадах, но при этом не создать ощущения, что успехов слишком мало, периметр зала должен находиться в пределах от C до D метров, включительно.
Прежде чем сделать окончательный выбор, организаторы олимпиады решили просмотреть по одному залу каждого подходящего размера. Залы с размерами Y × Z и Z × Y считаются одинаковыми. Чтобы понять необходимый объем работ по просмотру залов организаторы задались вопросом, сколько различных залов удовлетворяют приведенным выше ограничениям. Требуется написать программу, которая по заданным A, B, C и D определяет количество различных залов, площадь которых находится в пределах от A до B, а периметр — от C до D, включительно.

Формат входного файла
Входной файл содержит четыре разделенных пробелами целых числа: A, B, C и D (1<=A<=B<=10⁹ , 4<=C<=D<=10⁹ ).
Формат выходного файла
Выходной файл должен содержать одно число — искомое количество залов.

Ввод:
2 10 4 8
Вывод:
3

Пояснения к примеру
В примере ограничениям удовлетворяют залы следующих размеров: 1 × 2, 1 × 3, 2 × 2

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

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

Примеры тестов