Cho một mảng A gồm n số nguyên dương a₁, a₂, …, aₙ. Với mỗi giá trị aᵢ, hãy tính giá trị x + y, trong đó:

• x là chỉ số lớn nhất nhỏ hơn i thỏa mãn aₓ > aᵢ. Nếu không tồn tại x thỏa mãn thì x = -1;
• y là chỉ số nhỏ nhất lớn hơn i thỏa mãn aᵧ > aᵢ. Nếu không tồn tại y thỏa mãn thì y = -1.

Yêu cầu: Với mỗi phần tử aᵢ, hãy tính giá trị x + y tương ứng.

INPUT

• Dòng đầu tiên chứa số nguyên dương N (1 ≤ N ≤ 10⁶);
• Dòng thứ hai chứa N số nguyên dương a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10¹⁸).

OUTPUT

Gồm N số nguyên, số thứ i là kết quả tương ứng với phần tử aᵢ.

Ví dụ

Sample Input

5 
5 4 1 3 2

Sample Output

-2 0 6 1 3

Giải thích

Với từng vị trí i, ta có:

• Giá trị x tương ứng là: -1, 1, 2, 2, 4;
• Giá trị y tương ứng là: -1, -1, 4, -1, -1.

Do đó:

• Với i = 1: x = -1, y = -1 ⇒ x + y = -2;
• Với i = 2: x = 1, y = -1 ⇒ x + y = 0;
• Với i = 3: x = 2, y = 4 ⇒ x + y = 6;
• Với i = 4: x = 2, y = -1 ⇒ x + y = 1;
• Với i = 5: x = 4, y = -1 ⇒ x + y = 3.