/**
 * Definition for an inval.
 * type Interval struct {
 *	   Start int
 *	   End   int
 * }
 */
type SummaryRanges struct {
	is []Interval
}

/** Initialize your data structure here. */
func Constructor() SummaryRanges {
	return SummaryRanges{}
}

func (this *SummaryRanges) AddNum(val int) {
	n := len(this.is)
	if n == 0 {
		this.is = []Interval{{val, val}}
		return
	}
	beg, end := 0, n-1
	for beg <= end {
		mid := beg + (end-beg)/2
		if in := this.is[mid]; in.Start <= val && val <= in.End {
			return
		} else if val < in.Start {
			end = mid - 1
		} else if in.End < val {
			beg = mid + 1
		}
	}
	if beg == n {
		if val == this.is[n-1].End+1 {
			this.is[n-1].End++
		} else {
			this.is = append(this.is, Interval{val, val})
		}
	} else if beg == 0 {
		if val == this.is[0].Start-1 {
			this.is[0].Start--
		} else {
			nis := make([]Interval, n+1)
			nis[0] = Interval{val, val}
			copy(nis[1:], this.is)
			this.is = nis
		}
	} else {
		if l, r := val == this.is[beg-1].End+1, val == this.is[beg].Start-1; l && r {
			this.is[beg].Start = this.is[beg-1].Start
			copy(this.is[beg-1:], this.is[beg:])
			this.is = this.is[:n-1]
		} else if l {
			this.is[beg-1].End++
		} else if r {
			this.is[beg].Start--
		} else {
			nis := make([]Interval, n+1)
			copy(nis, this.is[:beg])
			nis[beg] = Interval{val, val}
			copy(nis[beg+1:], this.is[beg:])
			this.is = nis // Since append([]T, []T...) is rather inefficient, copy is the best choice
		}
	}
}

func (this *SummaryRanges) GetIntervals() []Interval {
	return this.is
}

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddNum(val);
 * param_2 := obj.GetIntervals();
 */