L-троміно#12969

L-троміно

2 секунди
512 мегабайтів
Дуже легка

Маємо прямокутну сітку з рядків і стовпців.

Також маємо необмежену кількість L-троміно:

Вам потрібно замостити сітку L-троміно так, щоб виконувалися такі умови.

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

Вхідні дані

У єдиному рядку задано ціле число — кількість стовпців сітки.

1 \le n \le 10^6.

Вихідні дані

Виведіть одне ціле число — мінімальну кількість непокритих клітинок сітки.

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

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

У другому прикладі мінімальна кількість непокритих клітинок дорівнює двом.