Oranges#508

Oranges

0,25 секунды
256 мегабайт
Medium

In this problem, you may need to use the Python 3.10 (PyPy) compiler instead of Python 3.13.

Given a coordinate line . On it, there are oranges at integer points x_1, x_2, \dots, x_n.

Suppose you start at coordinate . You need to collect all the oranges so that they are at coordinate . In second, you can move to an adjacent integer coordinate (i.e., take one step left or right). You can hold at most one orange at a time.

You need to find the minimum number of seconds required to collect all the oranges at coordinate .

You need to find this for each k = x_i (1 \leq i \leq n).

Input

The first line contains a single integer (1 \leq n \leq 10^5) — the number of oranges.

The second line contains integers x_1, x_2, \dots, x_n (1 \leq x_i \leq x_{i+1} \leq 10^9).

Output

Output integers.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Scoring

In this problem, each block is scored per test case.

  1. ( points): n = 1; x_i \leq 1\,000;

  2. ( points): n \leq 2; x_i \leq 1\,000;

  3. ( points): n \leq 3; x_i \leq 1\,000;

  4. ( points): n \leq 4; x_i \leq 1\,000;

  5. ( points): n \leq 100; x_i \leq 1\,000;

  6. ( points): n \leq 1\,000; x_i \leq 1\,000;

  7. ( points): x_i \leq 1\,000;

  8. ( points): no additional restrictions.