2021 年东华大学金马程序设计联赛

“Largest Rectangle in Histogram” problem is a classic problem. You are given an array of integers where each element represents the height of a bar in a histogram. A histogram is a graphical display of data using bars of different heights. The bars are placed in the exact same sequence as given in the array, and each of them has width 1. You need to find the area of the largest rectangle in the histogram.

But now Alice and Bob want to play a game on a histogram.They take alternating turns, and Alice is moving first.

Initially all cells are empty.During each turn, the player chooses three numbers:
$i,j,k(1\le i\le n,1\le j\le a_i-k,0\le k\le 3)$, then paints the following cells:$(i,j),(i,j+1),(i,j+2)\cdots (i,j+k)$. Remeber these cells must be empty area that has not been painted before.

You have to determine who wins if they both play optimally.