有 $n$ 个方块排列在一排。每个正方形都有一个向左或向右的脚印或一个洞，以 $<,>,.$ 表示。

Snuke，将重复下面的程序，直到不再有一个有洞的方块。

1. 以相等的概率随机选择一个有洞的正方形。
2. 填上所选正方形的洞，站在那里，并以相同的概率随机面向左边或右边。
3. 沿着Snuke所面对的方向一直走，直到他踩到一个有洞的方块或离开这排方块。

这里，方块和方向的选择是相互独立的。

当 Snuke 踩到一个方块（没有洞）时，该方块在他行走的方向上会有一个脚印。如果该方块已经有了一个脚印，那么它就会被抹去并被一个新的脚印取代。

当Snuke完成这些程序时，求向左的脚印数量的预期值。

• $n\leq10^5$