package main import ( "bufio" "fmt" "os" "sort" "strconv" "reflect" ) var wg = bufio.NewScanner(os.Stdin) const ( inf = int(1e18) initialBufSize = int(1e6) maxBufSize = int(1e6) mod = 998244353 ) var buf []byte = make([]byte, initialBufSize) func init() { wg.Split(bufio.ScanWords) wg.Buffer(buf, maxBufSize) } func nextInt() int { wg.Scan() i, e := strconv.Atoi(wg.Text()) if e != nil { panic(e) } return i } /* Monoid-Structure should be decleared some-where else. -> op(Monoid,Monoid)Monoid & ide()Monoid is required. */ type Monoid interface { Get() interface{} Op(Monoid) Monoid Ide() Monoid } type SegTree struct { monoid_type Monoid op func(Monoid) Monoid /* op */ e func() Monoid /*identity*/ d []Monoid _d []Monoid n int /* size*/ log int size int } func Gen(monoid Monoid, n int) (SegTree, bool) { seg := SegTree{monoid_type: monoid, op: monoid.Op, e: monoid.Ide, d: []Monoid{}, _d: []Monoid{}, n: 0, log: 0, size: 0} collect := true switch n > 0 { case true: seg.d = make([]Monoid, n) for i := range seg.d { seg.d[i] = seg.e() } default: collect = false return seg, collect } seg.n = len(seg.d) for ord := 0; (1 << ord) < seg.n; { ord++ seg.log = ord } seg.size = 1 << seg.log seg._d = make([]Monoid, 2*seg.size) for i := range seg._d { seg._d[i] = seg.e() } for i := 0; i < seg.n; i++ { seg._d[seg.size+i] = seg.d[i] } for i := seg.size - 1; i > 0; i-- { seg._update(i) } return seg, collect } func SliceGen(seg SegTree, array []Monoid) bool { ok := true if len(array) != seg.n { ok = false return ok } for _, v := range array { if reflect.TypeOf(seg.monoid_type) != reflect.TypeOf(v) { ok = false return ok } } for i, v := range array { seg.Set(i, v) } for i := seg.size - 1; i > 0; i-- { seg._update(i) } return ok } func (seg SegTree) _update(k int) { seg._d[k] = seg._d[2*k].Op(seg._d[2*k+1]) } func (seg SegTree) Set(p int, x Monoid) { //a[p] -> x p += seg.size seg._d[p] = x for i := 1; i <= seg.log; i++ { seg._update(p >> i) } } func (seg SegTree) Get(p int) Monoid { // a[p] return seg._d[p+seg.size] } func (seg SegTree) OverWrite(p int, f func(Monoid) Monoid) { p += seg.size m := seg._d[p] seg._d[p] = f(m) for i := 1; i <= seg.log; i++ { seg._update(p >> i) } } func (seg SegTree) Prod(l, r int) Monoid { //op(a[l..r)) sml := seg.e() smr := seg.e() l += seg.size r += seg.size for l < r { if l&1 == 1 { sml = sml.Op(seg._d[l]) l++ } if r&1 == 1 { r-- smr = seg._d[r].Op(smr) } l >>= 1 r >>= 1 } return sml.Op(smr) } func (seg SegTree) All_prod() Monoid { return seg._d[1] } type numbers struct { val, idx int } type monoid struct { val, cnt int } func (x monoid) Get() interface{} { return x } func (x monoid) Op(y Monoid) Monoid { return monoid{x.val + y.(monoid).val, x.cnt + y.(monoid).cnt} } func (x monoid) Ide() Monoid { return monoid{0, 0} } func main() { n := nextInt() a := make([]numbers, n) for i := 0; i < n; i++ { x := nextInt() a[i] = numbers{val: x, idx: i} } //left sort.Slice(a, func(i, j int) bool { if a[i].val > a[j].val { return true } else if a[i].val < a[j].val { return false } else { return a[i].idx > a[j].idx } }) seg, _ := Gen(monoid{}, n) left := make([]monoid, n) for _, v := range a { left[v.idx] = seg.Prod(0, v.idx).(monoid) seg.Set(v.idx, monoid{v.val, 1}) } //right sort.Slice(a, func(i, j int) bool { if a[i].val < a[j].val { return true } else if a[i].val > a[j].val { return false } else { return a[i].idx < a[j].idx } }) seg1, _ := Gen(monoid{}, n) right := make([]monoid, n) for _, v := range a { right[v.idx] = seg1.Prod(v.idx+1, n).(monoid) seg1.Set(v.idx, monoid{v.val, 1}) } ans := 0 for i := 0; i < n; i++ { if left[a[i].idx].cnt*right[a[i].idx].cnt > 0 { lval, lcnt := left[a[i].idx].val, left[a[i].idx].cnt rval, rcnt := right[a[i].idx].val, right[a[i].idx].cnt middle := a[i].val ans += lval*rcnt%mod + rval*lcnt%mod + middle*lcnt%mod*rcnt%mod ans %= mod } } fmt.Printf("%d\n", ans) }