Дано масив ~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