← Home
```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

type Hull struct {
	m []float64
	b []float64
	s []float64
}

func (h *Hull) f(i int, x float64) float64 {
	return h.m[i]*x + h.b[i]
}

func (h *Hull) intersect(m1, b1, m2, b2 float64) float64 {
	return (b2 - b1) / (m1 - m2)
}

func (h *Hull) AddLine(m, b float64) {
	n := len(h.m)
	if n == 0 {
		h.m = append(h.m, m)
		h.b = append(h.b, b)
		h.s = append(h.s, -1e300)
		return
	}
	for n > 0 {
		x := h.intersect(h.m[n-1], h.b[n-1], m, b)
		if x <= h.s[n-1] {
			h.m = h.m[:n-1]
			h.b = h.b[:n-1]
			h.s = h.s[:n-1]
			n--
			if n == 0 {
				break
			}
			continue
		}
		h.m = append(h.m, m)
		h.b = append(h.b, b)
		h.s = append(h.s, x)
		return
	}
	h.m = append(h.m, m)
	h.b = append(h.b, b)
	h.s = append(h.s, -1e300)
}

func (h *Hull) Query(x float64) float64 {
	l, r := 0, len(h.m)-1
	for l < r {
		mid := (l + r + 1) >> 1
		if h.s[mid] <= x {
			l = mid
		} else {
			r = mid - 1
		}
	}
	return h.f(l, x)
}

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	var Q int
	fmt.Fscan(in, &Q)

	var hull Hull
	var sum float64
	var n int
	var curMax float64

	for i := 0; i < Q; i++ {
		var t int
		fmt.Fscan(in, &t)
		if t == 1 {
			var x int64
			fmt.Fscan(in, &x)
			n++
			sum += float64(x)
			curMax = float64(x)
			k := float64(n)
			hull.AddLine(sum, -k)
		} else {
			x := curMax
			best := hull.Query(x)
			ans := best / x
			fmt.Fprintln(out, ans)
		}
	}
}
```