C - Various Kagamimochi
Source: atcoder
Difficulty: 300

Problem Statement
There are
N
mochi (rice cakes) arranged in ascending order of size.
The size of the
i
-th mochi
(1 \leq i \leq N)
is
A_i
.
Given two mochi
A
and
B
, with sizes
a
and
b
respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi
A
on top of mochi
B
if and only if
a
is at most half of
b
.
You choose two mochi out of the
N
mochi, and place one on top of the other to form one kagamimochi.
Find how many different kinds of kagamimochi can be made.
Two kagamimochi are distinguished if at least one of the mochi is different, even if the sizes of the mochi are the same.
Constraints
2 \leq N \leq 5 \times 10^5
1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
A_i \leq A_{i+1} \ (1 \leq i < N)
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1
A_2
\cdots
A_N
Output
Print the number of different kinds of kagamimochi that can be made.
Sample Input 1
6
2 3 4 4 7 10
Sample Output 1
8
The sizes of the given mochi are as follows:
In this case, you can make the following eight kinds of kagamimochi:
Note that there are two kinds of kagamimochi where a mochi of size
4
is topped by a mochi of size
2
, and two kinds where a mochi of size
10
is topped by a mochi of size
4
.
Sample Input 2
3
387 388 389
Sample Output 2
0
It is possible that you cannot make any kagamimochi.
Sample Input 3
32
1 2 4 5 8 10 12 16 19 25 33 40 50 64 87 101 149 175 202 211 278 314 355 405 412 420 442 481 512 582 600 641
Sample Output 3
388

C++ solution:
#include<bits/stdc++.h>
using namespace::std;

const int N = 500000 + 5;

int n;
int q;
int a[N];
int nxt[N];

void init() {
    int at = 1;
    for(int i = 1; i <= n; i++) {
        while(at <= n and a[i] > a[at] / 2) at += 1;
        nxt[i] = at;
    }
}

int main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    init();
    long long res = 0;
    for(int i = 1; i <= n; i++) {
        if(nxt[i] == n + 1) continue;
        res += n - nxt[i] + 1;
    }
    cout << res << endl;
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	var n int
	// fmt.Scan(&n)
	scanner.Scan()
	n, _ = strconv.Atoi(scanner.Text())
	// fmt.Println(n)

	a := make([]int, n)
	for i := 0; i < n; i++ {
		// fmt.Scan(&a[i])
		scanner.Scan()
		a[i], _ = strconv.Atoi(scanner.Text())
	}

	ans := 0
	cur_index := 0
	for i := 0; i < n; i++ {
		for a[cur_index] <= a[i]/2 {
			cur_index++
		}

		ans += cur_index
	}
	fmt.Println(ans)
}

Java solution:
import java.io.*;
import java.util.*;
// public class C_Various_Kagamimochi {
public class Main {

    static public void solve() throws IOException{
        int n = rd.nextInt();
        int[] a = new int[n];
        long ans = 0;
        for(int i = 0; i < n; i ++) a[i] = rd.nextInt();
        Arrays.sort(a);
        for(int l = 0, r = 0; r < n; r ++){
            while(a[l] <= a[r] / 2){
                l ++;
            }
            ans += l;
        }
        pw.println(ans);
    }
    public static void main(String[] args) throws IOException {
        int T = 1;
        // T = rd.nextInt();
        while(T --> 0) solve();
        pw.flush();pw.close();
    }

    static Read rd = new Read();
    static PrintWriter pw = new PrintWriter(System.out);
    static int inf = (int)2e9;
    static long INF = (long)2e18; 
}

class Read{
    StringTokenizer st;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String next() throws IOException{
        while (st == null || !st.hasMoreElements()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }
    int nextInt() throws IOException {return Integer.parseInt(next());}
    long nextLong() throws IOException {return Long.parseLong(next());}
    double nextDouble() throws IOException {return Double.parseDouble(next());}
    String nextLine() throws IOException {return br.readLine();}
}

JavaScript solution:
function Main(input) {
  const lines = input.trim().split('\n');
  const n = Number.parseInt(lines[0]);
  const a = lines[1].split(' ').map(v => Number.parseInt(v));
  let cnt = 0;
  let nextStart = 1;
  for (let i = 0; i < a.length; i ++) {
    if (a[i] * 2 > a[a.length - 1]) break;
    for (let j = nextStart; j < a.length; j ++) {
      if (a[i] * 2 <= a[j]) {
        nextStart = j;
        cnt += a.length - j;
        break;
      }
    }
  }
  console.log(cnt);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Python solution:
n = int(input())
a = list(map(int, input().split()))

cnt = 0
j = 1
for i in range(n-1):
    while j < n and 2 * a[i] > a[j]:
    	j += 1
    cnt += n-j

print(cnt)

Ruby solution:
n = gets().to_i
a = gets().split(' ').map{ |i| i.to_i }

ans = 0

j = 1
(n-1).times do |i|
  j += 1 if i == j
    
  while(a[i]*2 > a[j]) do
    j += 1

    if j == n
      p ans
      return
    end
  end

  ans += n - j
end

p ans