这里就给出四种方法。

Algorithm	Monotone queue	Left tree	Priority queue	Sort+
#1	0ms	0ms	1ms	0ms
#2	0ms	0ms	3ms	3ms
#3	0ms	0ms	3ms	3ms
#4	0ms	21ms	9ms	28ms
#5	1ms	20ms	10ms	62ms
#6	2ms	59ms	21ms	155ms
#7	2ms	43ms	21ms	233ms
#8	2ms	59ms	22ms	156ms
#9	1ms	60ms	21ms	228ms
#10	1ms	42ms	22ms	232ms
All	9ms	304ms	133ms	1100ms
	O(nlogn)	O(nlogn)	O(nlogn)	O(n^2)