Problem A. Square sort

Author:StdAlg
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:8 Mb

Statement

You are to write a program that receives a sequence of integer numbers and sorts it, i. e. writes out all elements in ascending order.

Input file format

Input file contains integer N — length of the sequnece, followed by N integer numbers — elements of the sequence.

Output file format

Output file must contain N integer numbers, which must be elements of the source sequence printed in ascending order.

Constraints

0 ≤ N ≤ 3000. Sequence elements are less than 109 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 4 3 10 3 1
1 3 3 4 10

Problem B. Lin-log sort

Author:StdAlg
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:8 Mb

Statement

You are to write a program that receives a sequence of integer numbers and sorts it, i. e. writes out all elements in ascending order.

Input file format

Input file contains integer N — length of the sequnece, followed by N integer numbers — elements of the sequence.

Output file format

Output file must contain N integer numbers, which must be elements of the source sequence printed in ascending order.

Constraints

0 ≤ N ≤ 100000. Sequence elements are less than 109 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 4 3 10 3 1
1 3 3 4 10

Задача C. Передовики производства

Автор:folklore
Входной файл: input.txt   Ограничение времени:2 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

На секретном оборонном заводе трудятся N рабочих. Каждый рабочий характеризуется своей производительностью — целым числом. С течением времени производительность некоторых рабочих может увеличиваться или уменьшаться. Вам задано число M — количество изменений производительности. Для каждого изменения известен номер рабочего, изменившего свою производительность и значение, на которое он она изменилась. Величина изменения может быть как положительной, так и отрицательной. Для планирования будущих достижений руководству завода необходимо всегда знать наибольшую производительность, достигнутую рабочими в данный момент.

Формат входного файла

В первой строке входного файла содержатся целые числа N M, разделенные пробелами. Далее следуют N чисел Ai, обозначающих производительность i-рабочего. Завершают входной файл M пар чисел Numi Vali, обозначающие номер рабочего, производительность которого изменилась и величину изменения соответственно.

Формат выходного файла

В выходной файл необходимо вывести M чисел — после каждого изменения производительности необходимо вывести наибольшую производительность по заводу.

Ограничения

(1 ≤ N, M ≤ 100000, 1 ≤ NumiN, −1000 ≤ Vali, Ai ≤ 1000)

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 4
7 4 9 
2 3
1 4
2 10
2 -10
9
11
17
11

0.025s 0.004s 11