10. **Poisonous Plants

Здравейте, Judge ми дава Time limit на последния тест на въпросната задача.

Условие:

You are given N plants in a garden. Each of these plants has been added with some amount of pesticide. After each day, if any plant has more pesticide than the plant at its left, being weaker (more GMO) than the left one, it dies. You are given the initial values of the pesticide and position of each plant. Print the number of days after which no plant dies, i.e. the time after which there are no plants with more pesticide content than the plant to their left.

Input

The input consists of an integer N representing the number of plants.
The next single line consists of N integers, where every integer represents the position and amount of pesticides of each plant. 1 ≤ N ≤ 100000
Pesticides amount on a plant is between 0 and 1000000000

Output

Output a single value equal to the number of days after which no plants die

Examples

Input

Output

Comments

6 5 8 4 7 10 9

Initially all plants are alive.

Plants = {(6, 1), (5, 2), (8, 3), (4, 4), (7, 5), (10, 6), (9, 7)}

Plants[k] = (i, j) => jth plant has pesticide amount = i.

After the 1st day, 4 plants remain as plants 3, 5, and 6 die.

Plants = {(6, 1), (5, 2), (4, 4), (9, 7)}

After the 2nd day, 3 plants survive as plant 7 dies. Plants = {(6, 1), (5, 2), (4, 4)}

After the 3rd day, 3 plants survive and no more plants die.

Plants = {(6, 1), (5, 2), (4, 4)}

After the 2nd day the plants stop dying.

Решение: https://pastebin.com/ghmRSbJq

Ще съм благодарен ако някой съумее да помогне.

Неприятна задача. Опитах да оптимизирам нещата като ползвам речник https://pastebin.com/m4MuDazE. Оптимизирането трябваше да дойде от това, че при махане на елемент от ArrayList, всички предмети след елемента трябва да се преместят с един индекс назад. Което при много голям вход от данни бави нещата. А пък при LinkedList макар и да е доста по-добре да се махат елементи, там пък достъпването на елемент по индекс е бавна операция (и лесното махате реално е от началото или края на колекцията). А пък при речниците добавянето на елемент, махането на елемент и достъпването на елемент са с константни или логаритмични сложности (т.е. бързички са). Но уви, пак гърми за време. Явно, освен че входът е обемен, самите данни са подадени в някакъв определен ред, който бави нещата. И алгоритъмът за решаване трябва да се промени.

Пускам код на един колега, който е взел максималните точки, но е леко странен алгоритъм и ще ти трябва време да зацепиш как точно работи https://pastebin.com/dTz5JBP3.