Lối tắt của Mike

Thành phố có $n$ giao lộ được đánh số từ $1$ đến $n$. Mike bắt đầu đi bộ từ nhà ở giao lộ số $1$.

Đi bộ từ giao lộ $i$ sang giao lộ $j$ tiêu tốn $|i-j|$ đơn vị năng lượng.

Ngoài ra, thành phố có $n$ lối tắt. Lối tắt thứ $i$ cho phép đi từ giao lộ $i$ đến giao lộ $a_i$ mà chỉ tốn đúng $1$ đơn vị năng lượng (lối tắt chỉ đi được một chiều: từ $i$ đến $a_i$, không đi ngược lại).

Mike đi theo một dãy giao lộ $p_1=1,p_2,\dots ,p_k$. Với mỗi bước từ $p_t$ sang $p_{t+1}$, chi phí là $1$ nếu $p_{t+1}=a_{p_t}$ (dùng lối tắt), ngược lại là $|p_t-p_{t+1}|$. Tổng năng lượng là tổng chi phí của tất cả các bước.

Với mỗi giao lộ $i$ từ $1$ đến $n$, hãy tìm tổng năng lượng nhỏ nhất để đi từ giao lộ $1$ đến giao lộ $i$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số giao lộ.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ mô tả các lối tắt.

Dữ liệu ra

In ra $n$ số nguyên $m_1,m_2,\dots ,m_n$, trong đó $m_i$ là tổng năng lượng nhỏ nhất để đi từ giao lộ $1$ đến giao lộ $i$.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $i\le a_i\le n$ và $a_i\le a_{i+1}$ với mọi $i$.

Ví dụ