題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 ABC388C Various Kagamimochi

Problem Statement

題目簡述

有 $N$ 個麻糬，大小已依非遞減順序排列。若選出的兩個麻糬大小分別為 $a$ 與 $b$ ，且上層麻糬大小 $a$ 不超過下層麻糬大小 $b$ 的一半，也就是 $2a \le b$ ，就能組成一個鏡餅。

請計算可以組成多少種不同的鏡餅。即使大小相同，只要使用的是不同顆麻糬，就視為不同組合。

Constraints

約束條件

$2 \le N \le 5 \times 10^5$
$1 \le A_i \le 10^9$
$A_i \le A_{i+1}$
所有輸入皆為整數

思路：同向雙指標

題目要求尋找滿足 $2a \le b$ 的配對 $(a, b)$ 。因為陣列已經排序，對於固定的下層麻糬 $b$ ，能作為上層的麻糬 $a$ 必然集中在陣列的最左側，形成一段前綴。

隨著下層麻糬變大，這段「合法前綴」的範圍只會向右擴張。因此，我們可以使用雙指標來解決：

遍歷每個麻糬作為下層（右指標）。
維護一個左指標，代表「目前可作為上層的麻糬數量」。
只要左指標指向的麻糬大小的兩倍不超過當前下層，左指標就向右移動。
擴張結束後，左指標的值恰好就是能與當前下層搭配的上層麻糬總數，將其累加至答案即可。

複雜度分析

時間複雜度： $\mathcal{O}(N)$ ，兩個指標最多各遍歷陣列一次。
空間複雜度： $\mathcal{O}(1)$ ，只需常數空間記錄指標與答案。

Code

N = int(input())
A = list(map(int, input().split()))

ans = left = 0
for right, a in enumerate(A):
    while A[left] * 2 <= a:
        left += 1
    ans += left
print(ans)