Contest problemset description

Pewnie umiesz już rozwiązywać proste nierówności, dlatego dzisiaj wyzwanie będzie nieco trudniejsze.

Twoim zadaniem jest policzenie liczby takich par dodatnich liczb całkowitych (x,y), dla których spełniona jest nierówność: x ⋅ y ⋅ (x+y) ≤ N.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się dodatnia liczba całkowita N.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita, będąca liczbą par spełniających nierówność.

Ograniczenia

1 ≤ N ≤ 10¹⁸.

W testach wartych łącznie 20% maksymalnej punktacji zachodzi: N ≤ 1000.

W testach wartych łącznie 50% maksymalnej punktacji zachodzi: N ≤ 1 000 000.

Przykład

17

6

100

29

Jasio niedawno odwiedził park linowy. Stojąc przed drewnianym mostkiem zaczął zastanawiać się, ile osób będzie jeszcze w stanie z niego skorzystać, zanim zostanie on oddany do remontu.

Jasio zna wytrzymałość każdej deski, tzn. ile osób może jeszcze na niej stanąć, zanim ta będzie musiała zostać wyremontowana. Deska, której wytrzymałość wynosi 0, nie musi zostać natychmiastowo wyremontowana, ale nikt więcej nie może już na niej stanąć. Ponadto Jasio zakłada, że każdy gość parku jest na tyle wysportowany, że może wykonać krok, o co najwyżej trzy deski w przód.

Twoim zadaniem jest obliczenie maksymalnej liczby osób, która będzie w stanie przejść przez mostek, zanim ten będzie musiał zostać oddany do remontu. Zakładamy, że każda osoba zaczyna stojąc przed mostkiem, a skończyć powinna za nim.

Wejście

W pierwszym wierszu wejścia znajduje się jedna dodatnia liczba całkowita N, będąca liczbą desek w mostku. W drugim wierszu wejścia znajduje się ciąg A₁, A₂, …, A_N, będący wytrzymałością kolejnych desek.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita, będąca maksymalną liczbą osób, która będzie w stanie przejść przez mostek.

Ograniczenia

3 ≤ N ≤ 500 000, 0 ≤ A_i ≤ 10⁸.

Przykład

6
1 1 0 2 1 0

2

3
4 6 8

18

Jasio uwielbia bawić się swoimi plastikowymi kulami. Niestety zawsze nadchodzi moment, gdy musi je ze smutkiem odłożyć do pudełka. Co ciekawe, pudełko na kule jest bardzo przemyślane – jest to plastikowa tuba, którą można otworzyć zarówno z dołu, jak i z góry.

Jasio wpadł na ciekawy pomysł: zamiast wkładać kule po kolei od góry, postanowił zrobić to w inny sposób. Przed włożeniem każdej kuli, Jasio najpierw obróci pudełko do góry nogami (oczywiście wcześniej zamknie je tak, aby kule się nie wysypały), a następnie włoży kulę od góry.

Twoim zadaniem jest znalezienie końcowej kolejności kul w pudełku.

Wejście

W pierwszym wierszu wejścia znajduje się dodatnia liczba całkowita N, będąca liczbą kul. W drugim wierszu wejścia znajduje się ciąg A₁, A₂, …, A_N, będący numerami kul, które Jasio będzie wkładał po kolei do pudełka.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinien znajdować się ciąg N liczb, będący końcową kolejnością kul (ich numerów) w pudełku.

Ograniczenia

1 ≤ N ≤ 200 000, 1 ≤ A_i ≤ 10⁹.

Przykład

4
1 2 3 4

4 2 1 3

3
3 2 1

1 3 2