Пусть N человек бегут вниз по эскалатору, причем i -ый пробегает одну ступеньку за t _i секунд. По технике безопасности бега по эскалатору, на эскалаторе запрещены "обгоны", то есть если A в процессе бега догнал человека B , который бежит с более низкой скоростью, то далее, до конца эскалатора, человек A бежит со скоростью человека B . Однако ступени эскалатора таковы, что на них может помещаться несколько человек одновременно. Ваша задача написать программу, которая рассчитает, когда закончит свой бег по эскалатору каждый бегущий человек.

Девочка Катя любит разные игры со словами. Недавно она придумала новую игру. Увидев где-либо написанное слово, она пытается придумать предложение, содержащее это слово в себе. Буквы увиденного слова должны идти в предложении по порядку, но не обязательно подряд. Например, увидев слово "LTIBE", она придумывает предложение "LET IT BE". Разумеется, Катя ищет кратчайшее предложение.

Ваша задача помочь Кате, автоматизировав игру.

В одном квадратном государстве жили квадратные люди. И все остальное в этом государстве было тоже квадратное. Так, Квадратная Дума приняла Квадратный Закон о земле. Согласно этому закону, любой житель государства имел право приобрести землю. Земля продавалась, естественно, квадратными участками. Длина стороны каждого участка выражалась натуральным числом метров. Приобретая участок земли со стороной a метров, покупатель платил a ² квадриков (местная валюта) и получал одно квадратное свидетельство о праве собственности на этот участок. Один житель этого государства решил вложить все свои N квадриков без остатка в покупку земли. Это безусловно можно было сделать, приобретя участки размером 1 * 1 метр. Но этот житель потребовал от агентства недвижимости минимизации количества покупаемых участков. «Так мне будет легче общаться с Квадратной Налоговой Инспекцией», - сказал он. Сделка состоялась.

Найдите, какое количество квадратных свидетельств он получил.

Дана последовательность попарно различных чисел A = [ A ₁ , A ₂ , ..., A _N ] , требуется переставить числа так, чтобы было верно A ₁ < A ₂ < ... < A _m > A _{m + 1} > ... > A _N (где m лежит между 1 и N включительно) Переставлять можно только пары соседних чисел, требуется минимизировать количество обменов.