## Problem A. Elementary arithmetic ≡

 Author: A. Zhuplev, A. Klenin Input file: input.txt Time limit: 1 sec Output file: output.txt Memory limit: 256 Mb

### Statement

Underwater arithmetic is very elementary. There are just two operations: WITH and WITHOUT which mean addition and subtraction respectively.

Underwater mathematicians did not yet invent brackets, so all expressions are calculated from right to left. For example, the expression 3 WITH 5 WITHOUT 4 WITHOUT 7 is calculated as (3 + (5 − (4 − 7))).

Scientists of Nearsea Institute of Underwater Arithmetic need a program to evaluate such expressions.

### Input file format

First line of input file contains a single integer N. Following 2 × N + 1 lines describe the expression. Odd lines contain integer operands, even lines contain operations.

### Output file format

Output file must contain a single integer — calculation result.

### Constraints

1 ≤ N ≤ 103

All operands are in range from 0 to 103.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1
2
WITH
3
5
2
3
10
WITHOUT
5
WITH
3
WITH
15
-13

## Problem B. Second Best ≡

 Author: A. Klenin Input file: input.txt Time limit: 2 sec Output file: output.txt Memory limit: 4 Mb

### Statement

Given the sequence of integers A1, A2, …, AN, find a number As such that there exists exactly one Am > As, and for all k ≠ m Ak ≤ As.

### Input file format

Input contains N followed by A1 A2… AN.

### Output file format

Output should contain a single integer — As, or 1 if no such number exists.

### Constraints

1 ≤ N ≤ 1000000, 0 ≤ Ai ≤ 109,

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
1 2 3
2
2
4
3 3 2 3
-1

## Задача C. Котенок Гав и сосиски ≡

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

### Условие

В распоряжение котенка Гава и щенка Шарика поступила лента из N сосисок. Они договорились есть ее с разных концов до тех пор, пока не встретятся. Гав съедает VGav сосисок в секунду, а Шарик — VSharik сосисок в секунду.

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

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

Входной файл содержит три целых числа: N — количество сосисок, VGav — скорость Гава, VSharik — скорость Шарика.

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

Выходной файл должен содержать два числа: сначала количество сосисок, целиком съеденных Гавом, а затем количество сосисок, целиком съеденных Шариком.

### Ограничения

1 ≤ N ≤ 108; 1 ≤ VGav, VSharik ≤ 10

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 1 2
3 6
2
2 5 3
1 0
3
2 5 5
1 1

## Задача D. И снова парад шушанчиков ≡

 Автор: А. Жуплев, А. Кленин Входной файл: input.txt Ограничение времени: 3 сек Выходной файл: output.txt Ограничение памяти: 128 Мб

### Условие

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

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

Крокодил хочет узнать, какую строку минимально возможной длины он может получить путём таких операций и просит вас написать программу, отвечающую на этот вопрос.

Например, если ряд задан строкой abbbwwbba, Гена может, например, поступить следующим образом: abbbwwbbaabwwbbaabwbbaabbbaabaEMPTY

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

Во входном файле содержится строка, задающая ряд шушанчиков.

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

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

### Ограничения

Исходная строка состоит из маленьких латинских букв, её длина не превышает 200000 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
abbbwwbba
EMPTY

## Задача E. Марсианская лингвистическая реформа ≡

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

### Условие

Алфавит марсианского языка состоит из строчных латинских букв. Буквам a, e, i, o, u, y соответствуют гласные звуки, остальным — согласные.

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

Марсиане просят написать программу, переводящую слова из старого в новый форматы.

Например, если старое слово имело вид eeaaeeuinfaormaaiatoyuaoics, то новое слово будет таким: eeaaeeuinfaormaaiatoyuaoics informatics.

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

Во входном файле содержится марсианское слово старого формата.

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

Выходной файл должен содержать марсианское слово нового формата.

### Ограничения

Длина слова находится в диапазоне от 1 до 100 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
eeaaeeuinfaormaaiatoyuaoics
informatics
2
aeeaaayyaaauaaiaaiaacm
acm
3
bzzt
bzzt

## Задача F. Слишком вложенные скобки ≡

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

### Условие

Дана правильная последовательность из круглых скобок. Требуется удалить из неё все скобки, находящиеся на глубине вложенности N и более. Например, в последовательности (()((()(())())))(((()))) выделены скобки, вложенные на 3 и более уровней.

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

Первая строка входного файла содержит число N. Вторая строка содержит правильную скобочную последовательность длиной от 2 до 10000 символов.

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

Выходной файл должен содержать укороченную скобочную последовательность.

1 ≤ N ≤ 5000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
()(())
()(())
2
3
(()((()(())())))(((())))
(()(()))((()))

## Задача G. Табуретки-1 ≡

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

### Условие

Для изготовления качественной табуретки необходимы 4 ножки одинаковой длины. На табуреткоизготовительную фабрику поступило N ножек, имеющих слегка различающиеся длины L1, L2, …, LN.

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

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

Входной файл содержит число N, за которым следуют N чисел Li — длины ножек. Все числа целые.

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

В выходной файл следует вывести единственное целое число — максимальное количество табуреток.

### Ограничения

1 ≤ N ≤ 10000, 1 ≤ Li ≤ 100.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
9
17 18 18 17 17 16 17 17 19
1

0.070s 0.004s 19