package main

import (
	"container/heap"
	"fmt"
	"sort"
)

type Person struct {
	id       int
	votTime  int
	votCount int
	heapIdx  int
}

type voteHeap []*Person

func (vh voteHeap) Len() int {
	return len(vh)
}

func (vh voteHeap) Swap(i, j int) {
	vh[i].heapIdx, vh[j].heapIdx = j, i
	vh[i], vh[j] = vh[j], vh[i]
}

func (vh voteHeap) Less(i, j int) bool {
	if vh[i].votCount != vh[j].votCount {
		return vh[i].votCount > vh[j].votCount
	}
	return vh[i].votTime > vh[j].votTime
}

func (vh *voteHeap) Push(x interface{}) {
	n := len(*vh)
	p := x.(*Person)
	p.heapIdx = n
	*vh = append(*vh, x.(*Person))
}

func (vh *voteHeap) Pop() interface{} {
	n := len(*vh)
	top := (*vh)[n-1]
	*vh = (*vh)[:n-1]
	return top
}

type TopVotedCandidate struct {
	persons   []int
	times     []int
	voteTable []int // 记录每个时刻领先的人物id
}

func Constructor(persons []int, times []int) TopVotedCandidate {
	tvc := TopVotedCandidate{}
	tvc.persons = persons
	tvc.times = times
	tvc.voteTable = make([]int, len(times), len(times))
	personMap := make(map[int]*Person)
	vh := make(voteHeap, 0, 0)
	heap.Init(&vh)
	for idx, time := range times {
		pId := persons[idx]
		if one, ok := personMap[pId]; ok {
			one.votCount++
			one.votTime = time
			heap.Fix(&vh, one.heapIdx)
		} else {
			one := &Person{
				pId,
				time,
				1,
				0,
			}
			personMap[pId] = one
			heap.Push(&vh, one)
		}
		tvc.voteTable[idx] = vh[0].id
	}
	return tvc
}

func (this *TopVotedCandidate) Q(t int) int {
	// 二分找idx
	n := len(this.times)
	idx := sort.Search(n, func(x int) bool {
		return this.times[x] > t
	}) - 1
	return this.voteTable[idx]
}

func main() {
	persons := []int{0, 1, 1, 0, 0, 1, 0}
	times := []int{0, 5, 10, 15, 20, 25, 30}
	tvc := Constructor(persons, times)
	fmt.Println(tvc.Q(3))
	fmt.Println(tvc.Q(12))
	fmt.Println(tvc.Q(25))
	fmt.Println(tvc.Q(15))
	fmt.Println(tvc.Q(24))
	fmt.Println(tvc.Q(8))
}