\documentclass[a4paper]{article}
\setlength{\textwidth}{19cm}
\setlength{\textheight}{27cm}
\setlength{\oddsidemargin}{-15mm}
\setlength{\evensidemargin}{-17mm}
\setlength{\topmargin}{-32mm}
\setlength{\baselineskip}{3em}

\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{cmap}

\renewcommand{\theenumi}{\Alph{enumi}}
\newcommand{\comptask}{\stepcounter{enumi}\theenumi$^*$}
\newcommand{\imptask}{\stepcounter{enumi}\theenumi$^\circ$}

\makeatletter

\def\verbsettings{\topsep=0pt\partopsep=0pt
\parsep=2pt\parskip=0pt\parindent=0pt\@totalleftmargin=0pt
\renewcommand{\baselinestretch}{0.8}\hsize=}

\def\myAlpha#1{{\@tempcnta=\csname c@#1\endcsname\relax
\advance\@tempcnta by -1\relax\@tempcntb=\@tempcnta\relax
\divide\@tempcntb by 26\relax\multiply\@tempcntb by 26\relax
\advance\@tempcnta by -\@tempcntb\relax\divide\@tempcntb by 26\relax
\advance\@tempcnta by 65\relax
\ifnum\@tempcntb>0\advance\@tempcntb by 64\relax\char\@tempcntb\fi
\char\@tempcnta}} % macro dlya odno- i dvuznachnykh bukvennykh napisanij

\def\@listi{} \def\@listI{} \itemsep=0pt \parskip=0pt 
\topsep=0pt \partopsep=0pt \parsep=0pt % ubivaem vse vertikalnye otstupy

\def\theenumi{\myAlpha{enumi}} % enumi --- eto schyotchik pervogo urovnya enumerate
	% theenumi --- tak budet pechatat'sya znachenie schyotchika
\def\labelenumi{\theenumi.} % tak dobavlyaetsya znak prepinaniya

\makeatother


\begin{document}

\thispagestyle{empty}
\Large

\center\textbf{Массивы.}
\bigskip
\flushleft
\normalsize

\emph{Обозначения}:
\parЭлементы массива --- целые числа, если не указано иное.
\parПримеры ввода массива с клавиатуры и создания массива, заполненного случайными значениями, можно посмотреть в \texttt{python-book}.
\parФраза \emph{"за один проход по массиву"} означает, что основной алгоритм должен быть записан при помощи цикла или циклов, суммарное количество итераций которых не больше, чем размер массива.
\parСимволом $^{\circ}$ помечены ключевые задачи, они используются в более сложных алгоритмах, как вспомогательные.
\parСимволом $^{*}$ помечены более сложные задачи.\par\textbf{Внимание!} Все задачи листочка требуется решить без применения к массивам и их срезам встроенных функций \texttt{max}, \texttt{min}, \texttt{find}, \texttt{count} и т.п., сложения списков и их срезов, а также без использования вспомогательных массивов, строк и иных структур данных (если только создание массива не требуется в условии задачи).
\parИспользование \texttt{max}, \texttt{min}, \texttt{abs} и прочих функций, принимающих на вход скаляры (т.е. не списки), разрешается и поощряется.
\parКроме того, изменять данный массив разрешается только в случае, если в условии задачи это указано явно (т.е. сказано, что разрешается его изменять или само изменение является целью задачи).
\bigskip

Считывать массив целых чисел, записанных в одну строку через пробел, можно так:
\par\texttt{x = list(map(int, input().split()))}
\bigskip
\parВыводить массив целых чисел в одну строку через пробел можно так:
\par\texttt{print(' '.join(map(str, x)))}
\bigskip
\large

\begin{enumerate}
\setlength{\itemsep}{7pt}
	\item\emph{Максимальный элемент и его номер}
\parДан список чисел. Выведите значение наибольшего элемента в списке, а затем индекс этого элемента в списке. Если наибольших элементов несколько, выведите индекс первого из них.
\parВ первой строке вводится натуральное число $N$, во второй --- $N$ целых чисел через пробел.
\parПрограмма должна вывести два числа --- ответ на вопрос задачи.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\verbsettings3cm
\begin{verbatim}
5
1 2 3 2 1
\end{verbatim}
\vskip2pt
}
&
\raise5pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt\makeatletter\@totalleftmargin=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
3 2
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item\emph{Поменять местами максимальный и минимальный элементы}
\parВ массиве поменять местами минимальный и максимальный элементы. Если минимальных несколько, взять тот, который имеет наименьший индекс. Если максимальных несколько, взять тот, который имеет наибольший индекс.
\parВ первой строке вводится натуральное число $N$, во второй --- $N$ целых чисел через пробел.
\parПрограмма должна изменить массив в соответствии с условием задачи и вывести его.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\verbsettings3cm
\begin{verbatim}
5
3 4 5 2 1
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
3 4 1 2 5
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item\emph{Линейный поиск}
\parНапишите программу, которая выводит номера элементов массива, равных данному числу.
\parВ первой строке задается одно натуральное число $N$, не превосходящее $1000$ --- размер массива.
\parВо второй строке вводятся $N$ чисел --- элементы массива (целые числа, не превосходящие по модулю $1000$).
\parВ третьей строке содержится одно целое число $x$, не превосходящее по модулю $1000$.
\parВывести номера элементов, равных данному, в порядке возрастания в одну строку через пробел. Нумерация элементов начинается с единицы. Если таких элементов нет, ничего выводить не нужно.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
5
1 2 3 4 5
3
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
3
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

\newpage
	\item\emph{Наименьший нечётный элемент}
\parНайдите значение наименьшего нечётного элемента массива. Если в массиве нет нечётных элементов --- выведите число $0$. Решите задачу при помощи одного прохода по массиву.
\parВ первой строке вводится натуральное число $N$, во второй --- $N$ целых чисел через пробел.
\parПрограмма должна вывести единственное число --- ответ на вопрос задачи.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
5
0 1 2 3 4
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
1
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item\emph{Больше своих соседей}
\parДан список чисел. Определите, сколько в этом списке элементов, которые больше двух своих соседей (т.е. таких элементов $x_i$, что $x_{i-1}<x_i>x_{i+1}$) и выведите количество таких элементов. Первый и последний элементы не имеют обоих соседей, поэтому учитываться не должны.
\parВ первой строке вводится натуральное число $N$, во второй --- $N$ целых чисел через пробел.
\parПрограмма должна вывести единственное число --- ответ на вопрос задачи.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
5
1 2 3 4 -2
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
1
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item\emph{Переставить соседние}
\parПереставьте соседние элементы массива (\texttt{A[0]} c \texttt{A[1]}, \texttt{A[2]} c \texttt{A[3]} и т.д.). Если элементов нечётное число, то последний элемент остается на своем месте.
\parВ первой строке вводится натуральное число $N$, во второй --- $N$ целых чисел через пробел.
\parПрограмма должна изменить массив в соответствии с условием задачи и вывести его.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
5
1 2 3 4 5
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
2 1 4 3 5
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item\emph{Наибольшая сумма двух соседних}
\parНайдите наибольшее значение суммы двух соседних элементов в данном массиве. Можно считать, что в массиве есть не менее двух элементов.
\parНа вход подаётся натуральное число $N (2\leqslant N\leqslant10^5)$. Затем на вход подаётся строка, в которой через пробел записаны $N$ целых чисел. Каждое число не превосходит по модулю $10^9$.
\parПрограмма должна вывести единственное число --- ответ на вопрос задачи.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
5
1 2 6 -5 4
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
8
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item\emph{Арифметическая прогрессия}
\parВыяснить --- являются ли целочисленные элементы данного массива элементами какой-то арифметической прогрессии, идущими подряд? Если да, вывести разность этой арифметической прогрессии, иначе вывести слово \texttt{NO}. Можно считать, что массив содержит не менее двух чисел.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
5
1 3 5 7 9
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
2
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\\

\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
5
1 2 3 4 6
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
NO
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item\emph{Ближайшее число}
\parНапишите программу, которая находит в массиве элемент, самый близкий по величине к  данному числу.
\parЕсли таких чисел несколько --- выведите любое.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
5
1 2 3 4 5
6
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
5
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

\newpage
	\item\emph{Сколько различных элементов в упорядоченном массиве}
\parДан массив, упорядоченный по неубыванию элементов в нём. Определите, сколько в нём различных элементов. Размер массива не превышает $10^5$.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
6
1 2 2 3 3 3
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
3
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item\emph{Максимальный элемент и их количество}
\parНайдите за один проход по массиву наибольшее значение в этом массиве и количество элементов, имеющих такое значение.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=4cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
7
8 7 7 5 5 8 5
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
8 2
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item\emph{Циклический сдвиг вправо}
\parЦиклически сдвиньте элементы списка вправо (\texttt{A[0]} переходит на место \texttt{A[1]}, \texttt{A[1]} на место \texttt{A[2]}, $\dots$, последний элемент \texttt{A[N - 1]} переходит на место \texttt{A[0])}.
\parПостарайтесь обойтись $N+1$ оператором присваивания (присваивание вида \texttt{a,b=b,a} считается за два).

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
5
1 2 3 4 5
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
5 1 2 3 4
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item\emph{Заменить на полусумму соседей}
\parЗамените все элементы массива, кроме первого и последнего на полусумму его соседних элементов (соседа слева и соседа справа).

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
5
3 5 2 1 7
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=4cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
3 2.5 3.0 4.5 7
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item[\imptask]\emph{Нули --- в конец}
\parНапишите программу, которая выполняет "<сжатие массива"> --- переставляет все нулевые элементы в конец массива. При этом все ненулевые элементы располагаются в начале массива в том же порядке.
\parВ первой строке вводится натуральное число $N\leqslant10^5$, во второй --- $N$ целых чисел через пробел.
\parПрограмма должна \emph{сначала} изменить массив в соответствии с условием задачи и вывести его.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
6
1 0 2 0 3 4
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
1 2 3 4 0 0
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item\emph{Пары равных элементов}
\parДан массив чисел. Посчитайте, сколько в нем пар элементов, равных друг другу. Считается, что любые два элемента, равные друг другу, образуют одну пару, которую необходимо посчитать.
\parИзменять массив нельзя, размер массива не превосходит $100$.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
5
1 2 3 2 3
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
2
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item\emph{Самое частое число}
\parДан массив. Не изменяя его и не используя дополнительные массивы, определите, какое число в этом списке встречается чаще всего.
\parЕсли таких чисел несколько, выведите любое из них.
\parРазмер массива не превосходит $10^3$.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
6
1 2 3 2 3 3
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
3
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large
\newpage

	\item\emph{Сколько различных элементов (общий случай)}
\parДан массив. Посчитайте, сколько в нём различных элементов, не изменяя самого массива и не используя вспомогательные массивы.
\parКоличество $N$ элементов в массиве не превосходит $10^5$ и в общем случае (с учётом ограничений в задаче) любое решение будет работать долго: количество операций пропорционально $N^2$. Тем не менее тесты составлены таким образом, чтобы рациональное решение проходило по времени.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
5
3 2 1 2 3
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
3
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large


	\item\emph{Уникальные элементы}
\parДан целочисленный массив. Выведите те его элементы, которые встречаются в массиве только один раз. Элементы нужно выводить в том порядке, в котором они встречаются в массиве.
\parКоличество $N$ элементов в массиве не превосходит $10^5$ и в общем случае (с учётом ограничений в задаче) любое решение будет работать долго: количество операций пропорционально $N^2$. Тем не менее тесты составлены таким образом, чтобы рациональное решение проходило по времени.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
6
1 2 2 3 3 3
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
1
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item\emph{Медиана}
\parВ массиве --- нечётное число элементов, при этом все элементы различны.
\parНайдите медиану списка: элемент, который стоял бы ровно посередине списка, если список отсортировать.
\parПри решении этой задачи нельзя модифицировать данный список (в том числе и сортировать его), использовать вспомогательные списки.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3.5cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
7
6 1 9 2 3 4 8
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
4
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item[\imptask]\emph{Строительство школы}
\parВ деревне все дома расположены вдоль одной улицы по одну сторону от неё. По другую сторону от этой улицы пока ничего нет, но скоро все будет --- школы, магазины, кинотеатры и т.д.
\parДля начала в этой деревне решили построить школу. Место для строительства школы решили выбрать так, чтобы суммарное расстояние, которое проезжают ученики от своих домов до школы, было минимально.
\parПлан деревни можно представить в виде прямой, в некоторых целочисленных точках которой находятся дома учеников. Школу также разрешается строить только в целочисленной точке этой прямой (в том числе разрешается строить школу в точке, где расположен один из домов --- ведь школа будет расположена с другой стороны улицы).
\parНапишите программу, которая по известным координатам домов учеников поможет определить координаты места строительства школы.
\parСначала а вход программе подаётся натуральное число $N$ --- число домов, в следующей строке записаны $N$ целых чисел --- координаты домов в порядке \emph{возрастания}.
\parПрограмма должна вывести целое число --- координату школы, суммарное расстояние от которой до всех домов наименьшее. Если таких координат несколько --- выведите любую.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
4
10 20 30 40
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
30
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large
\newpage

	\item[\imptask]\emph{Является ли массив подпоследовательностью другого}
\parДаны два массива. Определить, является ли второй массив подпоследовательностью первого. Выведите \texttt{YES}, если вторая последовательность является подпоследовательностью первой, иначе выведите \texttt{NO}.
\parСуммарное количество операций должно быть пропорционально сумме длин массивов, а не их произведению.
\parНа вход подаётся натуральное число $N (1\leqslant N\leqslant3\cdot10^5)$. Затем на вход подаётся строка, в которой через пробел записаны $N$ целых чисел. Каждое число не превосходит по модулю $10^9$.
\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
3
1 2 3
2
1 3
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
YES
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item[\imptask]\emph{Все простые в диапазоне}
\parДаны два числа $M$ и $N$, $2 \leqslant M \leqslant N \leqslant 10^6$.
\parВывести все простые числа от $M$ до $N$ включительно.
\parЕсли в указанном диапазоне простых чисел нет --- вывести число $-1$.
\parДля решения задачи надо получить массив логических переменных \texttt{primes}, такой, что \texttt{primes[k] = True} т и т.т., когда $k$ --- простое число. Сперва все значения равны \texttt{True}, затем при помощи решета Эратосфена изменить этот массив, чтобы он соответствовал его определению.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
2
5
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
2
3
5
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large


	\item[\imptask]\emph{Разворот части массива}
\parПереставьте в обратном порядке элементы массива, находящиеся между указанными индексами (включая и элементы с указанными индексами).
\parРешение следует оформить в виде функции с тремя параметрами: массив, левая граница и правая граница. Фунция должна изменять переданный массив в соответствии с условием.
\parНа вход подаётся три строки: в первой размер массив $N$, во второй $N$ целых чисел через пробел, в третьей два числа, разделённые пробелом: индексы левой и правой границ, соответственно.
\bigskip
\parДля чтения нескольких целочисленных переменных, записанных в одной строке через пробел можно пользоваться следующей конструкцией:
\par\texttt{a, b = map(int, input().split())}
\bigskip

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=5cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
10
0 5 2 4 9 -1 3 9 7 8
3 7
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=5cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
0 5 2 9 3 -1 9 4 7 8
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item\emph{Разворот чётного подмассива}
\parВ данном массиве обратить подмассив чётных чисел. Время работы должно быть пропорционально длине массива.
\parНа вход подаётся натуральное число $N (1\leqslant N\leqslant10^5)$. Затем на вход подаётся строка, в которой через пробел записаны $N$ целых чисел. Каждое число не превосходит по модулю $10^9$.
\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=5cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
10
6 10 3 6 3 8 2 3 7 3
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=5cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
2 8 3 6 3 10 6 3 7 3
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large
\newpage

	\item[\comptask]\emph{Большой сдвиг}
\parДан список из $N~(1\leqslant N\leqslant10^5)$ целых чисел и число $K~(|K|\leqslant10^5)$. Циклически сдвиньте список на $|K|$ элементов вправо, если $K$  положительное и влево, если отрицательное число.
\parРешение должно иметь сложность $O(N)$. В частности, время работы алгоритма не должно зависеть от $K$. Количество вспомогательной памяти $O(1)$.
\parВ этой задаче полезно ``подвигать'' элементы при циклических сдвигах на 2, 3, 4, 5, 6 в массиве из 12 элементов. Это может навести вас на соответствующий математический факт и алгоритм.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
5
5 3 7 4 6
3
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
7 4 6 5 3
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

	\item\emph{Минимальное число, непредставимое в виде суммы}
\parДан упорядоченный по неубыванию массив натуральных чисел. Найти минимальное натуральное число, не представимое в виде суммы нескольких элементов списка. Каждый элемент списка может быть взят не более одного раза. Список содержит не более $10^5$ элементов.
\parПридумайте очевидный инвариант для цикла и решение появится само собой.

\normalsize
\begin{tabular}{|c|c|}
\hline
Input & Output\\
\hline
\raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
5
1 1 2 5 15
\end{verbatim}
\vskip2pt
}
&
\raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt
\renewcommand{\baselinestretch}{0.8}
\begin{verbatim}
10
\end{verbatim}
\vskip2pt
}\\
\hline
\end{tabular}
\large

\end{enumerate}
\newpage

%\large\textbf{Задачи на использование встроенных функций работы со строками и массивами.}
%
%\begin{enumerate}
%\setlength{\itemsep}{-2pt}
%\setcounter{enumi}{22}
%	\item{Вывести количество слов в строке, содержащей только латинские буквы и пробелы.}
%	\item{Дана строка, содержащая предложения, заканчивающиеся точкой. Каждое предложение состоит из слов, содержащих только латинские буквы.
%\parВывести строку, содержащую исходные предложения без лишних пробелов. При этом все слова, кроме тех, с которых начинаются предложения, должны быть записаны только строчными буквами. Первое слово каждого предложения должно начинаться с заглавной буквы, остальные буквы --- строчные.}
%	\item{Задача 5 листочка по строкам (IP-адрес)}
%	\item{Задача 7 листочка по строкам (слова из данной строки, записанные в обратном порядке)}
%	\item{Дана строка. Вывести подстроку, заключённую между первым и последним символами \texttt{\#}.}
%\end{enumerate}

\end{document}