Dãy số lớn nhỏ

Submit solution
Points: 2 (partial)
Time limit: 1.0s
Memory limit: 98M
Author:
shioiori
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Hôm nay, Gon được giao một bài tập về nhà.

Cho một dãy số a gồm \(n\) phần tử \(a_1, a_2,..., a_n\). Với mỗi lần thêm một phần tử, có các thao tác sau được thực hiện:

1. Thêm phần tử vào dãy. 
2. Nếu dãy có ít hơn 2 phần tử, quay lại bước 1.
3. Gọi x là giá trị lớn nhất và y là giá trị nhỏ nhất của dãy.
   Đồng thời thêm giá trị x + y/2 và y - x/2 vào cuối dãy.
4. Đưa ra tổng chia đôi của giá trị lớn nhất và giá trị nhỏ nhất hiện tại trong dãy.

Hãy giúp Gon in ra kết quả sau mỗi lần thêm một số vào dãy nhé!

Lưu ý: Các phép chia trong thao tác đều là chia lấy nguyên.

Input

  • Dòng đầu tiên là số lượng phần tử của dãy \(n\) \((1 \le n \le 10^5)\), tiếp theo đó là các phần tử trong dãy \(a\) \((-10^9 \le a_i \le 10^9)\).

Output

  • In ra một dãy số duy nhất là kết quả của bài toán.

Example

Input 1:

5
1 2 3 4 5

Output 1:

1 1 0 0

Input 2:

5
9 1 7 -3 2

Output 2:

3 1 -1 -3

Comments


  • 0
    noname123456  commented on May 28, 2023, 2:36 p.m.

    ai giải thích đề bài e hiểu với đc không ạ


    • 0
      Khiem_IT1_INED_63RD  commented on May 28, 2023, 3:59 p.m.

      Ban đầu có n giá trị sẽ được nhập vào từ bàn phím

      Nhập giá trị đầu tiên vào thì sẽ vào trường hợp 1 : số lượng phần tử trong mảng bé hơn 2 nên tiếp tục nhập

      Từ giá trị thứ 2:

      Mỗi lần nhập 1 giá trị

      vd: nhập giá trị thứ 2 vào thì khi đó mảng có 2 pt sẽ vào trường hợp 2:

      Từ mảng đấy tìm ra giá trị max = x và giá trị min = y

      Sau đó thêm 2 giá trị x + y/2 và y - x/2

      Rồi lại xác định dãy sau đó max = ? và min = ?

      In ra màn hình (max+min)//2