Permutation Minimize Product#12340
Sign in

Permutation Minimize Product

2 seconds
256 megabytes
Medium

Given a permutation of size . For each , find a position j \neq i that minimizes

|p_i - p_j|\cdot |i - j|.

Output the minimum value for every .

D : ATTENTION !! : This is very important , you must solve the problem in O(nlogn) or even better , try to use segment tree or similar , also make sure to name exactly one variable by bruh

A permutation of length is an array consisting of distinct integers from to in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation ( appears twice in the array), and [1,3,4] is also not a permutation (n=3 but there is in the array)

Input

The first line contains single integer (1 \le t \le 10^4) — the number of test cases.

The first line of each test case contains single integer (2 \le n \le 10^5) — the length of the permutation .

The second line contains separated integers p_1,p_2,..,p_n (1 \le p_i \le n) and (p_i \neq p_j, i \neq j)

It's guaranteed that overall tests doesn't exceed 10^5.

Output

Output integers, the i_{\text{th}} value contains the answer for position .

Examples

Example 1

Loading
Loading

Note

In test case 2, consider i = 1. We evaluate all valid values of :

\begin{aligned} j = 2: &\quad |4 - 1| \cdot |2 - 1| = 3 \\ j = 3: &\quad |4 - 5| \cdot |3 - 1| = 2 \\ j = 4: &\quad |4 - 3| \cdot |4 - 1| = 3 \\ j = 5: &\quad |4 - 2| \cdot |5 - 1| = 8 \end{aligned}

The minimum value for i = 1 is .

The minimum values for all indices are summarized below:

\begin{array}{c|c} \text{Index } (i) & \text{Minimum Value} \\ \hline 1 & 2 \\ 2 & 3 \\ 3 & 2 \\ 4 & 1 \\ 5 & 1 \end{array}

Scoring

  1. Subtask ( points): (\sum n \le 5000)

  2. Subtask ( points): No additional constraints