leetcode-go/oj/bytedance-2019-spring/no3/reward.go

package main

import "fmt"

func main() {
	var N int
	fmt.Scan(&N)
	for cid := 0; cid < N; cid++ {
		var n int
		fmt.Scan(&n)
		a := make([]int, n)
		for i := range a {
			fmt.Scan(&a[i])
		}
		reward := make([]int, n)
		for i, idx := 0, 0; i < n+2; i++ {
			pre := (idx + n - 1) % n
			if a[pre] < a[idx] && reward[idx] <= reward[pre] {
				reward[idx] = reward[pre] + 1
			}
			idx = (idx + 1) % n
		}
		for i, idx := 0, 0; i < n+2; i++ {
			nxt := (idx + 1) % n
			if a[nxt] < a[idx] && reward[idx] <= reward[nxt] {
				reward[idx] = reward[nxt] + 1
			}
			idx = (idx + n - 1) % n
		}
		sum := 0
		for _, r := range reward {
			sum += r
		}
		fmt.Println(sum + n)
	}
}