Cho dãy vô hạn $a_1,a_2,a_3,\ldots$ được xác định như sau:

$$a_i = \begin{cases} 0 & \forall\, i < 2, \\[6pt] 2 & \forall\, 2 \leq i < 3, \\[6pt] 2a_{i-1} - a_{i-2} + 1 & \forall\, i \geq 3. \end{cases} $$

Đặt

$$S_i=\sum_{k=1}^{i}a_k$$

Yêu cầu

Cho n số nguyên dương $b_1,b_2,\ldots,b_n$. Tính $S_{b_1},S_{b_2},\ldots,S_{b_n}$.

Dữ liệu

Vào từ đầu vào chuẩn

• Dòng đầu tiên chứa số nguyên dương $n$.
• Dòng tiếp theo chứa $n$ số $b_1,b_2,\ldots,b_n$.

Kết quả

Ghi ra đầu ra chuẩn $n$ số nguyên $S_{b_1},S_{b_2},\ldots,S_{b_n}$. Các số trên cùng một dòng cách nhau bởi dấu cách.

Ví dụ

4
19 57 3 0

1311 32452 7 0

Giới hạn

Subtask 1 (20% số điểm): $n,b_i\le{10}^4$.

Subtask 2 (80% số điểm): $n,b_i\le{10}^6$.