#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_PARTS_MAX		100005									// 最大パーツ数

// 内部構造体 - パーツ情報
typedef struct Parts {
	int miWeight;												// 重さ
	long long mlSum;											// 合計数
} Parts;

// 内部変数
static int siPCnt;												// パーツ数
static Parts sz1Top[D_PARTS_MAX + 5];							// 上部パーツ
static Parts sz1Mdl[D_PARTS_MAX + 5];							// 中部パーツ
static Parts sz1Dwn[D_PARTS_MAX + 5];							// 下部パーツ

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpT, *szpFpA;
#endif

// パーツ取得
int
fGetParts(
	Parts *pzpParts				// <O> セット先
)
{
	int i;
	char lc1Buf[1024];

	for (i = 0; i < siPCnt; i++) {

		// 重さ
#ifdef D_TEST
		fscanf(szpFpT, "%d", &pzpParts[i].miWeight);
#else
		fscanf(stdin, "%d", &pzpParts[i].miWeight);
#endif

		// 合計数
		pzpParts[i].mlSum = 1;
	}
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpT);
#else
	fgets(lc1Buf, sizeof(lc1Buf), stdin);
#endif

	// 番兵
	pzpParts[siPCnt].miWeight = INT_MAX;
	pzpParts[siPCnt].mlSum = 0;

	return 0;
}

// ソート関数 - 重さ昇順
int
fSortFnc(
	const void *pzpVal1			// <I> 値１
	, const void *pzpVal2		// <I> 値２
)
{
	Parts *lzpVal1 = (Parts *)pzpVal1;
	Parts *lzpVal2 = (Parts *)pzpVal2;

	// 重さ昇順
	if (lzpVal1->miWeight > lzpVal2->miWeight) {
		return(1);
	}
	else if (lzpVal1->miWeight < lzpVal2->miWeight) {
		return(-1);
	}

	return 0;
}

// 合計数加算
int
fAddSum(
	Parts *pzpParts				// <I> 対象データ
)
{
	int i;

	for (i = siPCnt - 1; i >= 0; i--) {
		pzpParts[i].mlSum += pzpParts[i + 1].mlSum;
	}

	return 0;
}

// マッチング
int
fMatch(
	Parts *pzpFParts			// <I> セット元
	, Parts *pzpTParts			// <I> セット先
)
{
	int liFNo = siPCnt;
	int liTNo = siPCnt;
	while (1) {

		// セット先
		liTNo--;
		if (liTNo < 0) {
			break;
		}

		// セット元
		while (1) {
			if (liFNo == 0) {
				break;
			}
			if (pzpFParts[liFNo - 1].miWeight <= pzpTParts[liTNo].miWeight) {
				break;
			}
			liFNo--;
		}

		// 合計数
		pzpTParts[liTNo].mlSum *= pzpFParts[liFNo].mlSum;
	}

	return 0;
}

// 実行メイン
int
fMain(
	int piTNo					// <I> テスト番号 1～
)
{
	char lc1Buf[1024], lc1Out[1024];

	// テストファイルオープン
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo);
	szpFpT = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#endif

	// パーツ数取得
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpT);
#else
	fgets(lc1Buf, sizeof(lc1Buf), stdin);
#endif
	sscanf(lc1Buf, "%d", &siPCnt);

	// パーツ取得
	fGetParts(sz1Top);									// 上部
	fGetParts(sz1Mdl);									// 中部
	fGetParts(sz1Dwn);									// 下部

	// ソート
	qsort(sz1Top, siPCnt, sizeof(Parts), fSortFnc);		// 上部
	qsort(sz1Mdl, siPCnt, sizeof(Parts), fSortFnc);		// 中部
	qsort(sz1Dwn, siPCnt, sizeof(Parts), fSortFnc);		// 下部

	fAddSum(sz1Dwn);									// 下部 - 合計数加算
	fMatch(sz1Dwn, sz1Mdl);								// 中部 - マッチング(+下部)
	fAddSum(sz1Mdl);									// 中部 - 合計数加算
	fMatch(sz1Mdl, sz1Top);								// 上部 = マッチング(+中部)
	fAddSum(sz1Top);									// 上部 - 合計数加算

	// 結果セット
	sprintf(lc1Out, "%lld\n", sz1Top[0].mlSum);

	// 結果表示
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, lc1Out)) {
		siRes = -1;
	}
#else
	printf("%s", lc1Out);
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpT);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", piTNo);
	}
	else {
		printf("NG %d\n", piTNo);
	}
#endif

	return 0;
}

int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		fMain(i);
	}
#else
	fMain(0);
#endif

	return 0;
}



Measured memory_bytes: 6496