問題の要約

整数列 A_1..N が与えられます。 1 ≤ j < i ≤ N かつ A_j = A_i を満たす組 (i, j) の総数を求めてください。

解法のアイデア（高レベル）

配列を先頭から順に走査し、各値 v について「これまでに v が何回出現したか」を保持する Map（または連想配列）を使います。
現在の位置 i の値 v を見ると、過去に v が k 回出現していれば、(i, j) の組はちょうど k 個増えます。走査を最後まで行うと合計が答えになります。

式で書くと、最終的な答えは各値 v の出現回数 c_v に対して sum_v C(c_v, 2)（= sum_v c_v*(c_v-1)/2）と等価です。これは上の逐次加算の結果と一致します。

ステップ実行デモ（図で理解する）

配列（入力例）

このデモは配列 [30,10,30,20,10,30] を例に、各ステップで Map と合計がどう変化するかを示します。

状態（Map と合計）

値 (v)	出現回数

現在の合計 (組数): 0

次の要素を処理する際、もしその値 v の現在のカウントが k なら、合計は k 増え、その後 v のカウントを k+1 に更新します。

Step-by-step の説明（例）

初期: Map は空、合計=0。
1 番目（30）: Map[30]=0 → 合計 += 0 → Map[30]=1。
2 番目（10）: Map[10]=0 → 合計 += 0 → Map[10]=1。
3 番目（30）: Map[30]=1 → 合計 += 1 → Map[30]=2。
4 番目（20）: Map[20]=0 → 合計 += 0 → Map[20]=1。
5 番目（10）: Map[10]=1 → 合計 += 1 → Map[10]=2。
6 番目（30）: Map[30]=2 → 合計 += 2 → Map[30]=3。最終合計 = 4。

TypeScript 実装（提出用）

// TypeScript 5.1 / Node.js 18.16.1
// 高速入出力: fs
import * as fs from 'fs';

const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);

/**
 * 条件を満たす (i, j) の組数を数える関数
 * @param N - 配列の要素数
 * @param arr - 整数配列 A1...AN
 * @returns 組の総数（number）
 *
 * 時間計算量: O(N)（Map の get/set は平均 O(1)）
 * 空間計算量: O(U)（U は異なる値の個数。最悪で N）
 */
function countPairs(N: number, arr: number[]): number {
  const freq: Map = new Map();
  let count = 0;
  for (let i = 0; i < N; i++) {
    const v = arr[i];
    const prev = freq.get(v) ?? 0; // これまでの出現数
    count += prev; // prev 個だけ (i, j) の組が追加される
    freq.set(v, prev + 1);
  }
  return count;
}

const N = input[0];
const arr = input.slice(1);
console.log(countPairs(N, arr));

正当性の証明（簡潔に）

ある値 v の出現回数を c_v とすると、v によって作られる (i, j) の組の数は C(c_v, 2) = c_v*(c_v-1)/2 です。
逐次加算法は各 v の第 k 回目の出現（k を 1..c_v とする）で、その時点で過去に k-1 回出現しているため合計に k-1 を足します。よって合計は sum_{k=1..c_v}(k-1) = C(c_v,2) に一致します。

計算量と実装上の注意

時間: 一度の走査で Map の参照/更新を行うため O(N)。N = 100,000 でも余裕で間に合います（2 秒制限内）。
メモリ: Map に異なる値を保持します。最悪で N 個のエントリ。実装依存ですが、目安として 100,000 個の異なる整数 を Map に格納しても数MB〜十数MB 程度で収まることが多く、1024 MiB の上限には程遠いです。
Node.js + TypeScript 特有の注意: 標準入力の読み取りはまとめて行うのが高速です。fs.readFileSync(0, 'utf8') を使っています。

可視化 — インタラクティブ（内部実装）

下はこのドキュメント内で動く簡易デモです。配列を順に処理すると Map と合計がどのように変化するかを表示します。

まとめ

本問は Map による走査で簡潔に解けます。逐次加算の観点と組合せ C(n,2) の観点は同値であり、TypeScript の実装は提出用としてそのまま使えます。

もし、この HTML を 印刷用 PDF にしたり、別の入力例でインタラクティブに確認したければ、配列の部分を編集して試してみてください。追加で「異なる例のステップ図」や「より正確なメモリ見積もり」を入れることも可能です — ご希望あれば反映します。