Вам задано послідовність з ~n~ цілих чисел ~a_1, a_2, \ldots, a_n~. Якщо відсортувати ці числа за спаданням, то на першому місці опиниться найбільше число, а на другому місці — друге за величиною.

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

Виведіть друге за величиною число.

Вхідні дані

• Перший рядок містить одне ціле число ~n~ (~2 \le n \le 10^5~) — кількість чисел у послідовності.
• Другий рядок містить ~n~ цілих чисел ~a_1, a_2, \ldots, a_n~ (~-10^9 \le a_i \le 10^9~).

Вихідні дані

Виведіть одне ціле число — друге за величиною число в послідовності.

Приклади

Приклад 1

Вхідні дані:

5
3 7 7 2 5

Вихідні дані:

7

Пояснення: відсортована за спаданням послідовність: ~7, 7, 5, 3, 2~. Друге число — ~7~.

Приклад 2

Вхідні дані:

2
10 4

Вихідні дані:

4

Приклад 3

Вхідні дані:

4
-5 -1 -3 -2

Вихідні дані:

-2

Вам задано послідовність з ~n~ цілих чисел ~a_1, a_2, \ldots, a_n~ та число ~k~.

Потрібно порахувати кількість пар індексів ~(i, j)~ таких, що ~1 \le i < j \le n~ та ~a_i + a_j = k~.

Зверніть увагу, що пари розрізняються за індексами, а не за значеннями — якщо в масиві є декілька однакових чисел, кожна відповідна пара індексів рахується окремо.

Вхідні дані

• Перший рядок містить два цілих числа ~n~ і ~k~ (~1 \le n \le 2 \cdot 10^5~, ~-10^9 \le k \le 10^9~).
• Другий рядок містить ~n~ цілих чисел ~a_1, a_2, \ldots, a_n~ (~-10^9 \le a_i \le 10^9~).

Вихідні дані

Виведіть одне ціле число — кількість пар ~(i, j)~, для яких ~a_i + a_j = k~.

Гарантується, що відповідь поміщається в 64-бітний цілочисельний тип (long long).

Приклади

Приклад 1

Вхідні дані:

5 6
1 5 3 4 2

Вихідні дані:

2

Пояснення: масив ~a = [1, 5, 3, 4, 2]~. Пари індексів із сумою ~6~: ~(1,2)~, бо ~a_1+a_2=1+5=6~, та ~(4,5)~, бо ~a_4+a_5=4+2=6~. Разом — ~2~ пари.

Приклад 2

Вхідні дані:

6 10
5 5 5 5 5 5

Вихідні дані:

15

Пояснення: усі ~\binom{6}{2}=15~ пар дають суму ~10~.

Приклад 3

Вхідні дані:

1 0
100

Вихідні дані:

0

Дано прямокутний лабіринт розміром ~n \times m~ клітинок. Кожна клітинка є або вільною (.), або стіною (#). Крім того, рівно одна клітинка позначена S (старт) і рівно одна клітинка позначена F (фініш) — обидві ці клітинки вважаються вільними для проходу.

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

Визначте мінімальну кількість кроків, потрібну, щоб дістатися з S до F. Якщо це неможливо — виведіть ~-1~.

Вхідні дані

• Перший рядок містить два цілих числа ~n~ і ~m~ (~1 \le n, m \le 1000~, ~n \cdot m \le 10^6~) — кількість рядків і стовпців лабіринту.
• Далі йде ~n~ рядків по ~m~ символів у кожному — опис лабіринту. Кожен символ — це ., #, S або F. Гарантується, що символ S зустрічається рівно один раз, і символ F — теж рівно один раз.

Вихідні дані

Виведіть одне ціле число — мінімальну кількість кроків з S до F, або ~-1~, якщо шляху не існує.

Приклади

Приклад 1

Вхідні дані:

3 3
S..
.#.
..F

Вихідні дані:

4

Пояснення: один із найкоротших шляхів — ~(1,1) \to (2,1) \to (3,1) \to (3,2) \to (3,3)~ (рядок, стовпець, нумерація з 1), що займає рівно 4 кроки.

Приклад 2

Вхідні дані:

3 3
S#.
###
.#F

Вихідні дані:

-1

Пояснення: стіни повністю відділяють S від F.

Приклад 3

Вхідні дані:

1 2
SF

Вихідні дані:

1