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

Строение представляет собой абсолютно ровный коридор единичной ширины, в котором имеется N перегородок. Если расположить ось Х вдоль коридора, все перегородки будут находиться точно в ее целочисленных координатах с шагом 1, причем по ширине перегородки занимают весь коридор, а высоты могут отличаться. Создаваемый бассейн должен иметь максимально большой возможный объем при условии, что из всех имеющихся перегородок нужно оставить только две и увеличивать их высоту запрещено.

Формат ввода/вывода.  

Программа flooding считывает с клавиатуры (стандартного устройства ввода) целое число N (2<=N<=10⁵) – количество перегородок. Затем считывается N целых чисел а_i (1<=а_i<=10⁹) – высоты перегородок.

Программа flooding выводит на экран (стандартное устройство вывода) единственное число – максимальный объем создаваемого бассейна при описанных ограничениях.

Пример входных и выходных данных.

Задача Фазенда (hacienda).

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

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

Формат ввода/вывода.  

Программа hacienda считывает с клавиатуры (стандартного устройства ввода) целое число N (3<=N<=200) – количество деревьев в лесу. Затем считывается N пар целых чисел x_i,y_i (|x_i|,|y_i|<=10⁵) – координаты деревьев в лесу, причем никакие три дерева не находятся на одной прямой.

Программа hacienda выводит на экран (стандартное устройство вывода) единственное число – количество треугольных участков, не содержащих ни единого дерева.

Пример входных и выходных данных.

Задача Хитрый палиндром (pal333).

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

Формат ввода/вывода.  

Программа pal333 считывает с клавиатуры (стандартного устройства ввода) целое число N (1<=N<=100) – количество цифр числа. Затем считывается N цифр.

Программа pal333 выводит на экран (стандартное устройство вывода) единственное число – количество способов получения чисел-палиндромов, делящихся на число 333, из заданной последовательности цифр. Ответ должен быть выведен по модулю 10007. Палиндром может начинаться с ведущих нулей.

Пример входных и выходных данных.

Пояснение к примеру: из заданной последовательности цифр можно получить такие палиндромы, кратные 333: 0 (1-й ноль), 0 (2-й ноль), 00, 333 (1-я, 2-я и 3-я тройки), 333 (1-я, 2-я и 4-я тройки), 333 (1-я, 3-я и 4-я тройки), 333 (2-я, 3-я и 4-я тройки), 03330.