import "container/heap"

type Interval struct {
    start, end int
    index int
}

func (i *Interval) String() string {
    return fmt.Sprintf("[%d; %d] (%d)", i.start, i.end, i.maxDist())
}

func (i *Interval) maxDist() int {
    d := i.end - i.start - 1
    if d % 2 == 0 {
        d--
    }
    return d / 2
}

type IntervalsPQ []*Interval

func (pq IntervalsPQ) Len() int { return len(pq) }

func (pq IntervalsPQ) Less(i, j int) bool {
    iDist, jDist := pq[i].maxDist(), pq[j].maxDist()
    if iDist == jDist {
        ni, nj := pq[i].end - pq[i].start > 1, pq[j].end - pq[j].start > 1
        if ni == nj {
            return pq[i].start < pq[j].start
        }
        return ni
    }
    return iDist > jDist
}

func (pq IntervalsPQ) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *IntervalsPQ) Push(x interface{}) {
    interval := x.(*Interval)
    interval.index = len(*pq)
    *pq = append(*pq, interval)
}

func (pq *IntervalsPQ) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil  // avoid memory leak
    item.index = -1 // for safety
    *pq = old[:n-1]
    return item
}


type ExamRoom struct {
    intervals IntervalsPQ
    initialInterval *Interval
    n int
    mapping map[int][2]*Interval
}


func Constructor(N int) ExamRoom {
    return ExamRoom{intervals: make(IntervalsPQ, 0), n: N, mapping: make(map[int][2]*Interval)}
}


func (e *ExamRoom) Seat() int {
    // If there is not enough students to create an interval.
    if len(e.intervals) == 0 {
        if e.initialInterval == nil {
            e.initialInterval = &Interval{start: -1, end: e.n}
        }
        if e.initialInterval.start < 0 {
            // Put the student at position 0.
            e.initialInterval.start = 0
            m := e.mapping[0]
            m[1] = e.initialInterval
            e.mapping[0] = m
            return 0
        } else {
            e.initialInterval.end = e.n - 1
            // Add the interval to the heap.
            heap.Push(&e.intervals, e.initialInterval)
            // Update the mapping.
            m := e.mapping[e.n - 1]
            m[0] = e.initialInterval
            e.mapping[e.n - 1] = m
            return e.n - 1
        }
    }
    // Find the largest interval and split it into 2 intervals.
    interval := heap.Pop(&e.intervals).(*Interval)
    // Handle edge case intervals (left-most and right-most).
    if interval.start < 0 {
        interval.start = 0
        heap.Push(&e.intervals, interval)
        e.mapping[0] = [2]*Interval{nil, interval}
        return 0
    } else if interval.end >= e.n {
        interval.end = e.n - 1
        heap.Push(&e.intervals, interval)
        e.mapping[e.n - 1] = [2]*Interval{interval, nil}
        return e.n - 1
    }
    // Position for the new student.
    position := (interval.start + interval.end) / 2
    // Handle general case.
    left := &Interval{
        start: interval.start,
        end: position,
    }
    right := &Interval {
        start: position,
        end: interval.end,
    }
    // Put them both to the heap.
    heap.Push(&e.intervals, left)
    heap.Push(&e.intervals, right)
    // Update the mapping.
    m := e.mapping[interval.start]
    m[1] = left
    e.mapping[interval.start] = m

    m = e.mapping[interval.end]
    m[0] = right
    e.mapping[interval.end] = m

    e.mapping[position] = [2]*Interval{left, right}
    return position
}

func (e *ExamRoom) Leave(p int)  {
    m, ok := e.mapping[p]
    if !ok {
        panic(fmt.Sprintf("student %d not found in mapping", p))
    }
    left, right := m[0], m[1]
    // Merge intervals.
    if left != nil && right != nil {
        // Extend the left interval, get rid of the right one.
        left.end = right.end
        // Update the mapping.
        var m [2]*Interval
        if left.start >= 0 {
            m = e.mapping[left.start]
            m[1] = left
            e.mapping[left.start] = m
        }
        if left.end < e.n {
            m = e.mapping[left.end]
            m[0] = left
            e.mapping[left.end] = m
        }
        // Update the heap invariant for the left interval.
        heap.Fix(&e.intervals, left.index)
        // Remove the right interval from the heap.
        heap.Remove(&e.intervals, right.index)
    } else if left == nil {
        right.start = -right.end
        heap.Fix(&e.intervals, right.index)
    } else if right == nil {
        left.end = e.n - 1 + (e.n - 1 - left.start)
        heap.Fix(&e.intervals, left.index)
    } else {
        panic("removing non-existing student")
    }

    delete(e.mapping, p)
}


/**
 * Your ExamRoom object will be instantiated and called as such:
 * obj := Constructor(N);
 * param_1 := obj.Seat();
 * obj.Leave(p);
 */