Дано ~N~.

Вивести ~2^N~.

Обмеження

• ~0 \leq N \leq 30~
• ~N~ — ціле число.

Формат вхідних даних

Вхідний потік містить ціле число ~N~

Формат вихідних даних

У вихідний потік виведіть відповідь.

Приклад вхідних даних

3

Приклад вихідних даних

8

Приклад вхідних даних

30

Приклад вихідних даних

1073741824

Вам задано ціле число ~N~.

Вам потрібно вивести шаблон для заданого значення ~N~.

Наприклад, для ~N~=3 слід вивести:

3 3 3 2 2 2 1 1 1

3 3 2 2 1 1

3 2 1

Формат вхідних даних

Вхідний потік містить ціле число ~N~

Формат вихідних даних

У вихідний потік вивести ~N~ рядків згідно наведеного формату.

Обмеження

~1 \le N \le 40~

Приклад вхідних даних

2

Приклад вихідних даних

2 2 1 1 
2 1

Приклад вхідних даних

3

Приклад вихідних даних

3 3 3 2 2 2 1 1 1 
3 3 2 2 1 1 
3 2 1

Дано натуральне число ~N~.

Виведіть ~N~-й рядок трикутника Паскаля.

Формат вхідних даних

Вхідний потік містить ціле число ~N~

Формат вихідних даних

У вихідний потік вивести ~N~-й рядок трикутника Паскаля. Числа розділяти пропуском.

Обмеження:

• 1 ≤ N ≤ 30

Приклад вхідних даних

2

Приклад вихідних даних

1 1

Приклад вхідних даних

4

Приклад вихідних даних

1 3 3 1

Приклад вхідних даних

1

Приклад вихідних даних

1

Дано натуральне число ~N~. Знайдіть суму цифр факторіала числа ~N~.

Наприклад, при ~N~=5 ~5!=1 \times 2 \times 3 \times 4 \times 5 =120~ і сума цифр дорівнює 3.

Відомо, що 0!=1.

Формат вхідних даних

Вхідний потік містить ціле число $N$

Формат вихідних даних

У вихідний потік вивести відповідь

#Обмеження

• ~0 \le N \le 15~

Приклад вхідних даних

5

Приклад вихідних даних

3

Приклад вхідних даних

0

Приклад вихідних даних

1

Приклад вхідних даних

15

Приклад вихідних даних

17

У Степана є ~А~ яблук. Щоразу, коли Степан крикне, яблук стає більше в ~K~ разів.

Скільки мінімально разів Степан повинен крикнути щоб мати ~B~ або більше яблук?

Обмеження

• ~1 \leq A \leq B \leq 10^9~

• ~2 \leq K \leq 10^9~

• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Вхідний потік містить цілі числа ~A,B,K~

Числа розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть відповідь

Примітка

До прикладу 1:

Починаємо з одного яблука. Після першого крику Степана ми маємо два яблука; після його другого крику ми маємо чотири яблука.

Таким чином, йому потрібно крикнути принаймні двічі, щоб отримати чотири або більше яблук.

Приклад вхідних даних

1 4 2

Приклад вихідних даних

2

Приклад вхідних даних

7 7 10

Приклад вихідних даних

0

Приклад вхідних даних

31 415926 5

Приклад вихідних даних

6

Дано масив ~A~ з ~N~ додатних цілих чисел.

Ваше завдання --- знайти елементи, значення яких дорівнює значенню його індексу (Розглянемо індексацію з початком 1).

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число ~N~.

Наступний рядок містить ~N~ цілих чисел ~A_i~.

Числа розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести шукані елементи у порядку слідування їх у масиві. Числа розділяти пропуском.

Якщо таких чисел не знайдено, то виведіть -1.

Обмеження

~1 \le N \le 10^5~

~1 \le A_i \le 10^6~

Приклад вхідних даних

5
15 2 45 12 7

Приклад вихідних даних

2

Приклад вхідних даних

5
5 4 3 2 1

Приклад вихідних даних

3

Приклад вхідних даних

5
1 2 3 4 5

Приклад вихідних даних

1 2 3 4 5

Дано масив ~A~ довжиною ~N~ різних елементів.

Знайдіть у ньому третій за величиною елемент.

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число ~N~.

Наступний рядок містить ~N~ цілих чисел ~A_i~

Числа у другому рядку розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести шуканий елемент.

Обмеження

~1 \le N \le 10^5~

~1 \le A_i \le 10^5~

Приклад вхідних даних

5
2 4 1 3 5

Приклад вихідних даних

3

Приклад вхідних даних

5
2 3 4 5 7

Приклад вихідних даних

4

Дано масив ~A~, яки містить ~N~ цілих чисел.

Ваше завдання знайти лідерів у масиві. Елемент масиву є лідером, якщо він більший елементів, які розміщені праворуч від нього. Крайній правий елемент завжди є лідером.

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число ~N~.

Наступний рядок містить ~N~ цілих чисел ~A_i~

Числа у другому рядку розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести в одному рядку шукані елементи. Числа розділяти пропуском. Виводити елементи у порядку слідування у масиву.

Обмеження

~1 \le N \le 10^6~

~0 \le A_i \le 10^6~

Приклад вхідних даних

4
2 3 2 1

Приклад вихідних даних

3 2 1

Приклад вхідних даних

4
1 2 3 4

Приклад вихідних даних

4

Дано масив ~A~ із ~N~ цілих чисел і ціле число ~K~.

Знайдіть кількість пар елементів у масиві, сума яких дорівнює ~K~.

Формат вхідних даних

Перший рядок вхідного потоку містить цілі числа ~N~, ~K~.

Наступний рядок містить ~N~ цілих чисел ~A_i~

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести відповідь.

Обмеження:

• ~1 \le N \le 10^5~
• ~1 \le K \le 10^8~
• ~1 \le A_i \le 10^6~

Приклад вхідних даних

4 6
1 5 7 1

Приклад вихідних даних

2

Приклад вхідних даних

4 2
1 1 1 1

Приклад вихідних даних

6

Дано масив ~A~ з ~N~ цілих чисел.

Знайдіть суміжний підмасив (що містить принаймні одне число), який має максимальну суму.

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число ~N~.

Наступний рядок містить ~N~ цілих чисел ~A_i~

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести максимальну суму.

Обмеження:

• ~1 ≤ N ≤ 10^6~
• ~-10^7 ≤ A_i ≤ 10^7~

Приклад вхідних даних

5
1 2 3 -2 5

Приклад вихідних даних

9

Приклад вхідних даних

4
-1 -2 -3 -4

Приклад вихідних даних

-1